We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Moves to Seat Everyone

Number: 2148

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

There are n available seats and n students standing in a room. Given the seat positions and the initial student positions, the goal is to compute the minimum number of moves required to seat every student such that no two students share the same seat. A move consists of moving a student one unit to the left or right.

Key Insights

  • Sort both the seats and the students arrays.
  • Pair each student to the corresponding seat in the sorted order.
  • Summing the absolute differences between the paired positions gives the minimal total moves.
  • This greedy strategy minimizes the individual and overall movements.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if sorting in-place, otherwise O(n).

Solution

The solution involves first sorting both the seats and the students arrays. By pairing the smallest seat with the smallest student and so on, we ensure that the total distance moved by every student is minimized. The algorithm is straightforward: after sorting, iterate over the arrays, compute the absolute difference for each pair, and accumulate the results. The use of sorting guarantees the optimal minimal total moves.

Code Solutions

# Function to compute minimum moves required to seat all students
def min_moves_to_seat(seats, students):
    # Sort both lists to align seats with students in order
    seats.sort()
    students.sort()
    total_moves = 0
    # Iterate through the lists simultaneously
    for seat, student in zip(seats, students):
        # Add the absolute difference of the current paired positions
        total_moves += abs(seat - student)
    return total_moves

# Example usage
if __name__ == "__main__":
    seats = [3, 1, 5]
    students = [2, 7, 4]
    # Expected output: 4 moves
    print(min_moves_to_seat(seats, students))
← Back to All Questions