Watch 10 video solutions for Minimum Number of Moves to Seat Everyone, a easy level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 9,772 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |