Skip to main content
Talentd

Minimum Number of Moves to Seat Everyone - Solution & Explanation

EasyArrayGreedySortingCounting Sort16 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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 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.length
  • 1 <= n <= 100
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is in-place.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where m is the range of possible positions (maximum 100).
Space Complexity: O(m) due to frequency arrays.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Pairing

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is in-place.

Greedy with Frequency Arrays

Time Complexity: O(n + m), where m is the range of possible positions (maximum 100).
Space Complexity: O(m) due to frequency arrays.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and PairingO(n log n)O(1) to O(log n)General solution when positions are arbitrary and sorting is acceptable
Greedy with Frequency ArraysO(n + k)O(k)Best when position range is small; avoids sorting using counting technique

Video Solution

Minimum Number of Moves to Seat Everyone - Leetcode 2037 - Python • NeetCodeIO • 9,969 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Number of Moves to Seat Everyone with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays