How to Solve Minimum Number of Moves to Seat Everyone

Sort both the seats and students arrays to align positions optimally. Assign each student to the nearest available seat to minimize total moves. Summing the absolute differences between paired positions gives the minimum number of moves required for all students.

Problem Statement

You are given two arrays of length n: seats and students, representing the positions of n seats and n students in a room. Each student must occupy one seat, and multiple students cannot occupy the same seat.

In one move, a student can shift to an adjacent position by 1 unit. Return the minimum total moves needed to seat every student following the rule that no two students share a seat.

Examples

Example 1

Input: seats = [3,1,5], students = [2,7,4]

Output: 4

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

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

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

Solution Approach

Sort and Pair

Sort the seats and students arrays in ascending order. Pair each student with the corresponding seat by index to ensure minimal distance travel and optimal greedy assignment.

Calculate Moves

Iterate through the paired arrays and compute the absolute difference between each student position and their assigned seat. Sum these differences to get the total minimum moves.

Validate Greedy Choice

Ensure that no seat is assigned to multiple students after sorting. The invariant of one-to-one mapping between sorted arrays guarantees correctness, preventing overlap or unnecessary moves.

Complexity Analysis

Sorting takes O(n log n) and iterating to sum moves takes O(n), giving O(n log n) overall. Space is O(1) beyond input arrays since pairing is done in-place or with simple iteration.

What Interviewers Usually Probe

• The interviewer expects recognition of greedy assignment as the core pattern.
• They may hint at sorting both arrays to minimize distance without explicitly saying it.
• Look for opportunities to validate that no two students share a seat after pairing.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to sort both arrays leads to suboptimal total moves.
• Assigning students without checking one-to-one mapping can cause seat collisions.
• Counting moves incorrectly by using differences without absolute value produces wrong totals.

Follow-up variants

• Allowing multiple students per seat, requiring conflict resolution logic.
• Seats and students may have different lengths, necessitating extra handling.
• Introducing negative positions or larger ranges, requiring careful indexing or adjusted calculations.

How GhostInterview Helps

• GhostInterview identifies the greedy pattern and suggests sorting both arrays automatically.
• It calculates minimal moves efficiently, avoiding manual miscounting or collisions.
• The solver flags one-to-one mapping violations, ensuring valid seat assignments.

Topic Pages

• Array
• Greedy
• Sorting
• Counting Sort

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the minimum number of moves to seat everyone problem about?

It asks for moving each student to a seat with the least total moves using greedy assignment and absolute position differences.

How does the greedy choice pattern apply here?

Sorting both arrays ensures each student goes to the nearest available seat, minimizing total moves and validating invariants.

Can students occupy the same seat in this problem?

No, each seat must be occupied by exactly one student, and the algorithm must enforce this constraint.

What is the expected time complexity?

Sorting both arrays takes O(n log n) and summing moves takes O(n), resulting in O(n log n) overall.

Is sorting necessary for the solution?

Yes, sorting is critical to the greedy choice and invariant validation that ensures minimal total moves.