algoadvance

Leetcode Problem 2037: Minimum Number of Moves to Seat Everyone

You are given two arrays seats and students of equal length representing the positions of seats and students, respectively. The seats array is sorted in non-decreasing order. The task is to find the minimum number of moves required to seat every student in a seat such that each student moves to exactly one seat and each seat is occupied. One move consists of changing the position of a student by 1 unit to the left or right.

Example:

• Input:

  seats = [3, 1, 5]
  students = [2, 7, 4]
  

• Output: 4
  • Explanation:
    • Students move as follows:
      • Student at position 2 moves to position 1 (1 move).
      • Student at position 7 moves to position 5 (2 moves).
      • Student at position 4 moves to position 3 (1 move).
    • Total number of moves is 1 + 2 + 1 = 4.

Constraints:

1. n == seats.length == students.length
2. 1 <= n <= 100
3. 1 <= seats[i], students[i] <= 100

Clarifying Questions

1. Are there any constraints on the values within the seats and students array?
   • Yes, each value in both seats and students lies between 1 and 100.
2. Can a seat or student appear multiple times in the arrays?
   • Yes, there can be duplicate values as long as the array lengths and constraints are satisfied.
3. Is it guaranteed that seats are already sorted?
   • Yes, according to the problem statement.

Strategy

1. Since the position of seats and students can be in arbitrary order, first sort both arrays.
2. Then, pair each sorted student to the correspondingly indexed sorted seat.
3. Calculate the absolute difference between each student-seat pair to determine the number of moves required for each student to move to their seat.
4. Sum up these differences to get the total minimum number of moves required.

Code

def minMovesToSeat(seats, students):
    seats.sort()
    students.sort()
    
    # Calculate the total moves required
    total_moves = 0
    for i in range(len(seats)):
        total_moves += abs(seats[i] - students[i])
    
    return total_moves

# Test case
seats = [3, 1, 5]
students = [2, 7, 4]
print(minMovesToSeat(seats, students))  # Output: 4

Time Complexity

The primary operations that determine the time complexity of this solution are:

1. Sorting the seats array: O(n log n)
2. Sorting the students array: O(n log n)
3. A single iteration over the length of the arrays to calculate differences: O(n)

Therefore, the total time complexity is: [ \mathcal{O}(n \log n) + \mathcal{O}(n \log n) + \mathcal{O}(n) = \mathcal{O}(n \log n) ]

Given the constraints, this solution is efficient and suitable.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?