LeetCode 2037 - Minimum Number of Moves to Seat Everyone

LeetCode Problem 2037

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting, Counting Sort

Solution

Problem Understanding

This problem asks us to assign students to seats such that every student occupies exactly one seat and no two students share the same seat. Each student can move left or right on a number line, and every movement by one position costs exactly one move. The goal is to minimize the total number of moves required to seat everyone.

The input consists of two integer arrays:

• seats, where seats[i] represents the position of the i-th seat.
• students, where students[j] represents the position of the j-th student.

Both arrays have the same length n, meaning there are exactly as many students as seats. Since every seat must eventually be occupied and every student must sit somewhere, the problem becomes one of finding the best assignment between students and seats to minimize total movement cost.

The expected output is a single integer representing the minimum total number of moves needed so that every student occupies a unique seat.

The constraints are relatively small:

• 1 <= n <= 100
• 1 <= seats[i], students[j] <= 100

These constraints tell us two important things. First, the number of elements is small, meaning even moderately inefficient approaches could still work in practice. Second, positions are bounded between 1 and 100, which hints that techniques like counting sort may also be viable.

One important aspect of the problem is that multiple seats or students may begin at the same position. For example, there may be two seats at position 2 or multiple students standing together. A naive implementation that assumes unique positions could fail. Fortunately, the problem guarantees that the number of students equals the number of seats, so a valid assignment always exists.

Several edge cases are worth considering upfront. If all students are already sitting at seat positions, the answer should be 0. Duplicate positions for seats or students must be handled correctly. Cases where all students are far away from seats should still compute the minimum efficiently. Since positions are always positive and small, we do not need to worry about negative coordinates or overflow issues.

Approaches

Brute Force Approach

A brute force approach would try every possible assignment of students to seats and compute the total movement cost for each arrangement. Since each student can potentially sit in any seat, this becomes a permutation problem.

For every permutation of seat assignments, we calculate:

$$\sum |student_i - assignedSeat_i|$$

Then we return the minimum among all possible assignments.

This approach is guaranteed to be correct because it exhaustively checks every valid pairing and chooses the one with the smallest total movement cost.

However, the downside is performance. There are n! possible assignments. Even for moderate values of n, factorial growth becomes infeasible. With n = 100, this approach is completely impossible.

Optimal Greedy Approach

The key insight is that the minimum movement cost is achieved when we sort both arrays and pair corresponding elements.

Why does sorting help?

Imagine seats and students positioned along a number line. If we pair students and seats in an arbitrary order, paths may cross, creating unnecessary movement. For example:

Seats:     [1, 5]
Students:  [4, 2]

If we assign:

4 → 1
2 → 5

the total cost becomes:

|4 - 1| + |2 - 5| = 3 + 3 = 6

But after sorting:

Seats:     [1, 5]
Students:  [2, 4]

we pair:

2 → 1
4 → 5

giving:

|2 - 1| + |4 - 5| = 1 + 1 = 2

Sorting aligns nearby students with nearby seats, preventing inefficient cross assignments.

Since sorting dominates the runtime, this solution runs efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Tries every possible student-to-seat assignment
Optimal	O(n log n)	O(1) or O(n)	Sort both arrays and pair corresponding positions

Algorithm Walkthrough

1. Sort the seats array in ascending order.

Sorting ensures seats are processed from left to right. Nearby seats become adjacent, which helps construct an optimal assignment. 2. Sort the students array in ascending order.

This aligns students from left to right in the same order as seats. 3. Initialize a variable total_moves to 0.

This variable accumulates the total number of movements required. 4. Iterate through both arrays simultaneously.

Since both arrays are sorted and have equal length, pair the student at index i with the seat at index i. 5. Compute the movement cost for each pair.

For each index:

abs(seats[i] - students[i])

Add this value to total_moves. 6. Return total_moves.

After processing every student-seat pair, the accumulated sum represents the minimum total movement cost.

Why it works

The correctness comes from a greedy matching property on a number line. After sorting, matching the i-th smallest student with the i-th smallest seat avoids crossing assignments. Any crossing assignment can be swapped to reduce or maintain total cost, never increasing it. Therefore, sorted matching always produces an optimal minimum-cost arrangement.

Python Solution

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()

        total_moves = 0

        for seat_position, student_position in zip(seats, students):
            total_moves += abs(seat_position - student_position)

        return total_moves

The implementation follows the algorithm exactly.

First, both arrays are sorted in ascending order. This step is crucial because it ensures that nearby students are matched with nearby seats.

Next, total_moves is initialized to store the running sum of movement costs.

The zip() function is used to iterate through both sorted arrays simultaneously. At each iteration, we compute the absolute difference between the student's position and the seat's position. This value represents the number of moves required for that student.

Finally, the accumulated result is returned as the minimum number of moves required.

Go Solution

package main

import "sort"

func minMovesToSeat(seats []int, students []int) int {
	sort.Ints(seats)
	sort.Ints(students)

	totalMoves := 0

	for i := 0; i < len(seats); i++ {
		diff := seats[i] - students[i]

		if diff < 0 {
			diff = -diff
		}

		totalMoves += diff
	}

	return totalMoves
}

The Go implementation mirrors the Python approach closely. The main difference is sorting, which uses sort.Ints().

Go does not provide a built in abs() function for integers, so we manually compute the absolute value by checking whether the difference is negative.

Since the constraints are very small and values are bounded by 100, integer overflow is not a concern. Empty slices are also naturally handled, though the problem guarantees at least one seat and one student.

Worked Examples

Example 1

Input:

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

Step 1: Sort both arrays

Array	Sorted Result
Seats	[1,3,5]
Students	[2,4,7]

Step 2: Pair corresponding positions

Index	Seat	Student	Moves
0	1	2	`
1	3	4	`
2	5	7	`

Total:

1 + 1 + 2 = 4

Output:

4

Example 2

Input:

seats = [4,1,5,9]
students = [1,3,2,6]

Step 1: Sort both arrays

Array	Sorted Result
Seats	[1,4,5,9]
Students	[1,2,3,6]

Step 2: Pair corresponding positions

Index	Seat	Student	Moves
0	1	1	0
1	4	2	2
2	5	3	2
3	9	6	3

Total:

0 + 2 + 2 + 3 = 7

Output:

7

Example 3

Input:

seats = [2,2,6,6]
students = [1,3,2,6]

Step 1: Sort both arrays

Array	Sorted Result
Seats	[2,2,6,6]
Students	[1,2,3,6]

Step 2: Pair corresponding positions

Index	Seat	Student	Moves
0	2	1	1
1	2	2	0
2	6	3	3
3	6	6	0

Total:

1 + 0 + 3 + 0 = 4

Output:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting both arrays dominates the runtime
Space	O(1) or O(n)	Depends on the sorting implementation

The runtime complexity comes primarily from sorting the two arrays, which costs O(n log n) each. The final traversal through both arrays takes only O(n) time.

The space complexity depends on the language and sorting implementation. Python's Timsort may use additional memory internally, while Go's sorting implementation also uses some auxiliary space. Ignoring implementation details, the algorithm itself only uses a few extra variables.

Test Cases

solution = Solution()

assert solution.minMovesToSeat([3, 1, 5], [2, 7, 4]) == 4  # Example 1
assert solution.minMovesToSeat([4, 1, 5, 9], [1, 3, 2, 6]) == 7  # Example 2
assert solution.minMovesToSeat([2, 2, 6, 6], [1, 3, 2, 6]) == 4  # Example 3

assert solution.minMovesToSeat([1], [1]) == 0  # Single seat and student
assert solution.minMovesToSeat([100], [1]) == 99  # Maximum distance

assert solution.minMovesToSeat([1, 2, 3], [1, 2, 3]) == 0  # Already aligned
assert solution.minMovesToSeat([3, 2, 1], [1, 2, 3]) == 0  # Unsorted but matching

assert solution.minMovesToSeat([2, 2, 2], [1, 2, 3]) == 2  # Duplicate seats
assert solution.minMovesToSeat([1, 2, 3], [2, 2, 2]) == 2  # Duplicate students

assert solution.minMovesToSeat([10, 20, 30], [1, 2, 3]) == 54  # Large movement
assert solution.minMovesToSeat([5, 5, 5], [5, 5, 5]) == 0  # All same position

Test	Why
[3,1,5], [2,7,4]	Verifies example case
[4,1,5,9], [1,3,2,6]	Tests varied distances
[2,2,6,6], [1,3,2,6]	Ensures duplicates are handled
[1], [1]	Smallest valid input
[100], [1]	Maximum positional distance
[1,2,3], [1,2,3]	Already optimal arrangement
[3,2,1], [1,2,3]	Confirms sorting correctness
[2,2,2], [1,2,3]	Duplicate seats
[1,2,3], [2,2,2]	Duplicate students
[10,20,30], [1,2,3]	Large movement values
[5,5,5], [5,5,5]	All entities at same location

Edge Cases

One important edge case occurs when all students are already seated optimally. For example:

seats = [1,2,3]
students = [1,2,3]

A buggy implementation might unnecessarily rearrange assignments and increase movement cost. Sorting preserves the natural alignment, and every absolute difference becomes zero.

Another important case is duplicate seat positions or duplicate student positions. For example:

seats = [2,2,6,6]
students = [1,3,2,6]

Some implementations incorrectly assume unique values and may overwrite assignments or use invalid matching logic. Since the algorithm only relies on sorted ordering, duplicates are naturally handled without any special logic.

A third important edge case involves highly unbalanced distances:

seats = [100]
students = [1]

The answer is simply the absolute difference, 99. Since movement cost is based on distance, the implementation correctly handles large gaps by using abs(seat - student).

Finally, unsorted input can easily trip up naive implementations. Consider:

seats = [10,1]
students = [2,9]

Without sorting, pairing by index gives:

|10 - 2| + |1 - 9| = 16

After sorting:

|1 - 2| + |10 - 9| = 2

Sorting is what guarantees the optimal assignment.