Minimum Number of Moves to Seat Everyone solution and explanation
Google
9 more videos on this problem
Minimum Number of Moves to Seat Everyone - Leetcode 2037 - PythonNeetCodeIO · 13:06 · 9K views
Minimum Number of Moves to Seat Everyone | Counting Sort | Sort | Leetcode 2037 | codestorywithMIKcodestorywithMIK · 21:39 · 6K views
2037. Minimum Number of Moves to Seat Everyone | Greedy | Counting SortAryan Mittal · 12:40 · 5K views
2037. Minimum Number of Moves to Seat Everyone (Leetcode Easy)Programming Live with Larry · 5:00 · 2K views
✅Minimum Number of Moves to Seat Everyone - LeetCode 2037 - Arrays - Sorting - Explained in DetailLeet Logics · 5:17 · 1K views
Minimum Number of Moves to Seat Everyone in 30 seconds - Leetcode 2037Top SWE · 0:18 · 1K views
LeetCode 2037 : Minimum Number of Moves to Seat Everyone | Solution in JAVAAmit Manjarly · 4:02 · 1K views
LeetCode 2037 : Minimum Number of Moves to Seat Everyone | Solution in C++Amit Manjarly · 4:16 · 1K views
LeetCode 2037 - Minimum Number of Moves to Seat EveryoneAlpha-Code · 7:14 · 117 views
Leetcode 2037: Minimum Number of Moves to Seat EveryoneAlgorithms Casts · 6:45 · 114 views
The problem
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:
- Increase or decrease the position of the
ithstudent by1(i.e., moving theithstudent from positionxtox + 1orx - 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] <= 100
Approach overview
Problem 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 1: Sorting and Pairing
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.
def min_moves_to_seat(seats, students):
seats.sort()
students.sort()
return sum(abs(s - st) for s, st in zip(seats, students))
seats = [3, 1, 5]
students = [2, 7, 4]
print(min_moves_to_seat(seats, students))import java.util.Arrays;
public class Solution {
public int minMovesToSeat(int[] seats, int[] students) {
Arrays.sort(seats);
Arrays.sort(students);
int result = 0;
for (int i = 0; i < seats.length; i++) {
result += Math.abs(seats[i] - students[i]);
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] seats = {3, 1, 5};
int[] students = {2, 7, 4};
System.out.println(sol.minMovesToSeat(seats, students));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {
std::sort(seats.begin(), seats.end());
std::sort(students.begin(), students.end());
int result = 0;
for (size_t i = 0; i < seats.size(); ++i) {
result += std::abs(seats[i] - students[i]);
}
return result;
}
int main() {
std::vector<int> seats = {3, 1, 5};
std::vector<int> students = {2, 7, 4};
std::cout << minMovesToSeat(seats, students) << std::endl;
return 0;
}function minMovesToSeat(seats, students) {
seats.sort((a, b) => a - b);
students.sort((a, b) => a - b);
return seats.reduce((acc, seat, i) => acc + Math.abs(seat - students[i]), 0);
}
const seats = [3, 1, 5];
const students = [2, 7, 4];
console.log(minMovesToSeat(seats, students));#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void * a, const void * b) {
return (*(int*)a - *(int*)b);
}
int minMovesToSeat(int* seats, int seatsSize, int* students, int studentsSize) {
qsort(seats, seatsSize, sizeof(int), cmpfunc);
qsort(students, studentsSize, sizeof(int), cmpfunc);
int result = 0;
for (int i = 0; i < seatsSize; i++) {
result += abs(seats[i] - students[i]);
}
return result;
}
int main() {
int seats[] = {3,1,5};
int students[] = {2,7,4};
int n = sizeof(seats)/sizeof(seats[0]);
printf("%d\n", minMovesToSeat(seats, n, students, n));
return 0;
}using System;
class Solution {
public int MinMovesToSeat(int[] seats, int[] students) {
Array.Sort(seats);
Array.Sort(students);
int result = 0;
for (int i = 0; i < seats.Length; i++) {
result += Math.Abs(seats[i] - students[i]);
}
return result;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] seats = {3, 1, 5};
int[] students = {2, 7, 4};
Console.WriteLine(sol.MinMovesToSeat(seats, students));
}
}Using sort() for both lists, we zip them to calculate the sum of absolute differences between paired elements, which gives the minimum moves.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since no extra space is used beyond input.
Approach 2: Greedy with Frequency Arrays
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.
def min_moves_to_seat(seats, students):
seat_count = [0] * 101
student_count = [0] * 101
for seat in seats:
seat_count[seat] += 1
for student in students:
student_count[student] += 1
i = j = movements = 0
while i < 101 and j < 101:
if seat_count[i] > 0 and student_count[j] > 0:
min_count = min(seat_count[i], student_count[j])
movements += abs(i - j) * min_count
seat_count[i] -= min_count
student_count[j] -= min_count
if seat_count[i] == 0: i += 1
if student_count[j] == 0: j += 1
return movements
seats = [3, 1, 5]
students = [2, 7, 4]
print(min_moves_to_seat(seats, students))import java.util.HashMap;
public class Solution {
public int minMovesToSeat(int[] seats, int[] students) {
int[] seatCount = new int[101], studentCount = new int[101];
for (int seat : seats) seatCount[seat]++;
for (int student : students) studentCount[student]++;
int i = 0, j = 0, moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
int minCount = Math.min(seatCount[i], studentCount[j]);
moves += Math.abs(i - j) * minCount;
seatCount[i] -= minCount;
studentCount[j] -= minCount;
}
if (seatCount[i] == 0) i++;
if (studentCount[j] == 0) j++;
}
return moves;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] seats = {3, 1, 5};
int[] students = {2, 7, 4};
System.out.println(sol.minMovesToSeat(seats, students));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {
std::vector<int> seatCount(101, 0), studentCount(101, 0);
for (int seat : seats) seatCount[seat]++;
for (int student : students) studentCount[student]++;
int i = 0, j = 0, moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
int min_count = std::min(seatCount[i], studentCount[j]);
moves += abs(i - j) * min_count;
seatCount[i] -= min_count;
studentCount[j] -= min_count;
}
if (seatCount[i] == 0) i++;
if (studentCount[j] == 0) j++;
}
return moves;
}
int main() {
std::vector<int> seats = {3, 1, 5};
std::vector<int> students = {2, 7, 4};
std::cout << minMovesToSeat(seats, students) << std::endl;
return 0;
}function minMovesToSeat(seats, students) {
let seatCount = Array(101).fill(0);
let studentCount = Array(101).fill(0);
for (let seat of seats) seatCount[seat]++;
for (let student of students) studentCount[student]++;
let i = 0;
let j = 0;
let moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
const minCount = Math.min(seatCount[i], studentCount[j]);
moves += Math.abs(i - j) * minCount;
seatCount[i] -= minCount;
studentCount[j] -= minCount;
}
if (seatCount[i] === 0) i++;
if (studentCount[j] === 0) j++;
}
return moves;
}
const seats = [3, 1, 5];
const students = [2, 7, 4];
console.log(minMovesToSeat(seats, students));#include <stdio.h>
#include <stdlib.h>
int minMovesToSeat(int* seats, int seatsSize, int* students, int studentsSize) {
int seatCount[101] = {0}, studentCount[101] = {0};
for (int i = 0; i < seatsSize; i++)
seatCount[seats[i]]++;
for (int i = 0; i < studentsSize; i++)
studentCount[students[i]]++;
int i = 0, j = 0, moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
int min_count = seatCount[i] < studentCount[j] ? seatCount[i] : studentCount[j];
int shift = abs(i - j);
moves += shift * min_count;
seatCount[i] -= min_count;
studentCount[j] -= min_count;
}
if (seatCount[i] == 0) i++;
if (studentCount[j] == 0) j++;
}
return moves;
}
int main() {
int seats[] = {3, 1, 5};
int students[] = {2, 7, 4};
int n = sizeof(seats) / sizeof(seats[0]);
printf("%d\n", minMovesToSeat(seats, n, students, n));
return 0;
}using System;
class Solution {
public int MinMovesToSeat(int[] seats, int[] students) {
int[] seatCount = new int[101];
int[] studentCount = new int[101];
foreach (int seat in seats) seatCount[seat]++;
foreach (int student in students) studentCount[student]++;
int i = 0, j = 0, moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
int minCount = Math.Min(seatCount[i], studentCount[j]);
moves += Math.Abs(i - j) * minCount;
seatCount[i] -= minCount;
studentCount[j] -= minCount;
}
if (seatCount[i] == 0) i++;
if (studentCount[j] == 0) j++;
}
return moves;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] seats = {3, 1, 5};
int[] students = {2, 7, 4};
Console.WriteLine(sol.MinMovesToSeat(seats, students));
}
}Establish frequency accounts for seats and students. Traverse each array hyper-sequentially to compute corresponding minimal moves using a pairwise greedy matching algorithm.
Time Complexity: O(n + m), with m as declared possible positions.
Space Complexity: O(m), to store frequency arrays.
Approach 3: Sorting
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.
function minMovesToSeat(seats: number[], students: number[]): number {
seats.sort((a, b) => a - b);
students.sort((a, b) => a - b);
return seats.reduce((acc, seat, i) => acc + Math.abs(seat - students[i]), 0);
}func minMovesToSeat(seats []int, students []int) (ans int) {
sort.Ints(seats)
sort.Ints(students)
for i, a := range seats {
b := students[i]
ans += abs(a - b)
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn min_moves_to_seat(mut seats: Vec<i32>, mut students: Vec<i32>) -> i32 {
seats.sort();
students.sort();
let n = seats.len();
let mut ans = 0;
for i in 0..n {
ans += (seats[i] - students[i]).abs();
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Pairing | Time Complexity: O(n log n) due to sorting. |
| Greedy with Frequency Arrays | Time Complexity: O(n + m), with m as declared possible positions. |
| Sorting | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Number of Moves to Seat Everyone easy or hard?
Minimum Number of Moves to Seat Everyone is classified as an Easy problem on LeetCode with a high acceptance rate. The main insight is recognizing that sorting both arrays and pairing them greedily minimizes total movement.
Minimum Number of Moves to Seat Everyone Python/Java solution
In Python or Java, the typical implementation sorts both arrays and loops through them to sum absolute differences. Python uses built-in sorting with `sorted()` or `list.sort()`, while Java uses `Arrays.sort()`. After sorting, a single pass computes the minimal total moves.
How to solve Minimum Number of Moves to Seat Everyone in O(n)?
Use a counting or frequency array approach when seat and student positions fall within a small bounded range. Count how many seats and students appear at each position, then sweep from left to right while tracking the imbalance between them. The cumulative imbalance represents how many students must move across positions. This produces an O(n + k) time solution without sorting.
What is the best approach for Minimum Number of Moves to Seat Everyone?
The most common solution sorts both the seats and students arrays and pairs them in order. After sorting, compute the sum of absolute differences between corresponding elements. This greedy matching works because crossing assignments always increase total movement. The time complexity is O(n log n) due to sorting.
Is Minimum Number of Moves to Seat Everyone asked at Google/Amazon/Meta?
Problems involving greedy pairing and distance minimization appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the core pattern—sorting two arrays and minimizing pairwise distance—is a common interview concept.
What data structure is used in Minimum Number of Moves to Seat Everyone?
The solution primarily uses arrays. The basic approach sorts two arrays and iterates through them once. The optimized version uses additional frequency arrays, similar to counting sort, to track how many seats and students appear at each position.
What is the time complexity of Minimum Number of Moves to Seat Everyone?
The standard approach runs in O(n log n) time because both arrays are sorted before pairing. A more optimized solution uses frequency arrays and runs in O(n + k), where k is the maximum position value. Space complexity is O(1) for sorting (ignoring recursion stack) or O(k) for the counting approach.