Minimum Number of Moves to Seat Everyone — Solution
Minimum Number of Moves to Seat Everyone solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Number of Moves to Seat Everyone is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Greedy, Counting Sort
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n seats and n students in a room. seats[i] is the position of the i-th seat and students[j] is the position of the j-th student.
In one move you may shift a student one position left or right. Return the minimum number of moves needed to seat every student, with no two students in the same seat.
Example 1
Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Example 2
Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Example 3
Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Constraints
1 <= seats.length <= 40seats.length == students.length1 <= seats[i], students[j] <= 100
Hints for Minimum Number of Moves to Seat Everyone
Hint 1
Sort both lists and match them position by position.
Hint 2
Crossing two assignments never helps — swapping them back cannot increase the total distance.
Hint 3
The answer is the sum of the absolute differences of the matched pairs.
How to solve Minimum Number of Moves to Seat Everyone
Sort both lists and match them index by index; the answer is the sum of absolute differences.
Approach
- Sort
seatsandstudents. - Sum
|seats[i] - students[i]|.
Why it works
If two assignments cross (a left student to a right seat and vice versa), uncrossing them never increases the total distance, so the sorted matching is optimal.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- The lists have equal length by the statement; no padding is needed.
Reference solution
Python
def minMovesToSeat(seats, students) -> int:
return sum(abs(a - b) for a, b in zip(sorted(seats), sorted(students)))Java
public static int minMovesToSeat(int[] seats, int[] students) {
int[] a = Arrays.copyOf(seats, seats.length);
int[] b = Arrays.copyOf(students, students.length);
Arrays.sort(a);
Arrays.sort(b);
int total = 0;
for (int i = 0; i < a.length; i++) total += Math.abs(a[i] - b[i]);
return total;
}C++
int minMovesToSeat(vector<int>& seats, vector<int>& students) {
vector<int> a = seats;
vector<int> b = students;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int total = 0;
for (size_t i = 0; i < a.size(); i++) total += abs(a[i] - b[i]);
return total;
}JavaScript
var minMovesToSeat = function(seats, students) {
const a = seats.slice().sort(function(x, y) { return x - y; });
const b = students.slice().sort(function(x, y) { return x - y; });
let total = 0;
for (let i = 0; i < a.length; i++) total += Math.abs(a[i] - b[i]);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms