There are n availabe seats and n students standing in a room. You are given an array seats of length n, where seats[i] is the position of the ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.
You may perform the following move any number of times:
ith student by 1 (i.e., moving the ith student from position x to x + 1 or x - 1)Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.
Note that there may be multiple seats or students in the same position at the beginning.
Example 1:
Input: seats = [3,1,5], students = [2,7,4] Output: 4 Explanation: The students are moved as follows: - The first student is moved from position 2 to position 1 using 1 move. - The second student is moved from position 7 to position 5 using 2 moves. - The third student is moved from position 4 to position 3 using 1 move. In total, 1 + 2 + 1 = 4 moves were used.
Example 2:
Input: seats = [4,1,5,9], students = [1,3,2,6] Output: 7 Explanation: The students are moved as follows: - The first student is not moved. - The second student is moved from position 3 to position 4 using 1 move. - The third student is moved from position 2 to position 5 using 3 moves. - The fourth student is moved from position 6 to position 9 using 3 moves. In total, 0 + 1 + 3 + 3 = 7 moves were used.
Example 3:
Input: seats = [2,2,6,6], students = [1,3,2,6] Output: 4 Explanation: Note that there are two seats at position 2 and two seats at position 6. The students are moved as follows: - The first student is moved from position 1 to position 2 using 1 move. - The second student is moved from position 3 to position 6 using 3 moves. - The third student is not moved. - The fourth student is not moved. In total, 1 + 3 + 0 + 0 = 4 moves were used.
Constraints:
n == seats.length == students.length1 <= n <= 1001 <= seats[i], students[j] <= 100Problem Overview: You are given two arrays: seats and students. Each element represents a position on a line. A student can move left or right, and each step costs one move. The task is to assign every student to a unique seat while minimizing the total number of moves.
Approach 1: Sorting and Pairing (Time: O(n log n), Space: O(1) to O(log n))
The key observation is that crossing assignments increase total distance. If the smallest student position goes to the smallest seat, the second smallest to the second smallest, and so on, the total movement stays minimal. Start by sorting both seats and students. Iterate through both arrays and compute abs(seats[i] - students[i]) for each pair. Add the distances to get the final cost. This approach relies on sorting and a simple greedy pairing strategy.
Sorting ensures that nearby positions are matched together instead of creating long cross movements. The algorithm performs one pass after sorting, so the dominant cost is the sorting step. This solution is clean, easy to implement, and works well for typical interview constraints.
Approach 2: Greedy with Frequency Arrays (Time: O(n + k), Space: O(k))
The constraints limit positions to a small range, which makes a counting-style solution possible. Instead of sorting, build two frequency arrays where freqSeat[x] and freqStudent[x] count how many seats and students appear at position x. Traverse the positions from left to right and track the difference between seats and students seen so far.
When there are extra students at earlier positions, they must move to future seats. When there are extra seats, future students move backward. Maintain a running imbalance and accumulate the absolute value of this difference at each position. This effectively simulates the minimal movement required without explicitly pairing every seat and student. The technique combines greedy reasoning with a counting sort style frequency traversal.
This approach runs in linear time with respect to the number of students plus the value range. It avoids sorting entirely and is optimal when the coordinate range is small.
Recommended for interviews: The sorting and pairing solution is what most interviewers expect first. It demonstrates understanding of greedy matching and produces a clear O(n log n) solution. The frequency-array method shows deeper optimization and familiarity with range-based counting techniques on arrays. Mention the sorting solution first, then discuss the linear-time improvement if the position range is bounded.
This approach relies on sorting both the seats and students arrays. After sorting them, we pair the i-th seat with the i-th student. The sum of absolute differences between corresponding elements gives us the minimum number of moves required.
We define a comparison function cmpfunc for sorting. Using qsort, both arrays are sorted. The absolute differences between paired elements from sorted arrays are summed to get the minimum moves.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is in-place.
This approach involves creating frequency arrays or maps for both seats and students positions. Align students to seats by finding the closest available seat iteratively, simulating a greedy approach.
Initialize frequency arrays for both seats and students. Then, use two pointers to traverse and match the closest available seat to each student, updating movements accordingly.
Time Complexity: O(n + m), where m is the range of possible positions (maximum 100).
Space Complexity: O(m) due to frequency arrays.
Sort both arrays, then traverse the two arrays, calculate the distance between each student's seat and their actual seat, and add all the distances to get the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the arrays seats and students.
| Approach | Complexity |
|---|---|
| Sorting and Pairing | Time Complexity: O(n log n) due to sorting. |
| Greedy with Frequency Arrays | Time Complexity: O(n + m), where m is the range of possible positions (maximum 100). |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Pairing | O(n log n) | O(1) to O(log n) | General solution when positions are arbitrary and sorting is acceptable |
| Greedy with Frequency Arrays | O(n + k) | O(k) | Best when position range is small; avoids sorting using counting technique |
Minimum Number of Moves to Seat Everyone - Leetcode 2037 - Python • NeetCodeIO • 9,772 views views
Watch 9 more video solutions →Practice Minimum Number of Moves to Seat Everyone with our built-in code editor and test cases.
Practice on FleetCode