Problem Description

You have n available seats and n students standing in a room. Each seat has a specific position given in the array seats where seats[i] represents the position of the i-th seat. Similarly, each student has a starting position given in the array students where students[j] represents the position of the j-th student.

You can move students to assign them to seats. In each move, you can:

• Move any student one position to the left or right (from position x to x+1 or x-1)

Your goal is to assign each student to a seat such that:

• Every student sits in exactly one seat
• No two students share the same seat
• The total number of moves is minimized

The problem asks you to return the minimum total number of moves required to achieve this arrangement.

Important Notes:

• Multiple seats can initially be at the same position
• Multiple students can initially be at the same position
• Since there are exactly n seats and n students, a valid assignment is always possible

Example: If seats = [3, 1, 5] and students = [2, 7, 4]:

• After sorting: seats = [1, 3, 5] and students = [2, 4, 7]
• Optimal assignment: student at position 2 → seat at position 1 (1 move), student at position 4 → seat at position 3 (1 move), student at position 7 → seat at position 5 (2 moves)
• Total moves = |2-1| + |4-3| + |7-5| = 1 + 1 + 2 = 4

Intuition

The key insight is to think about this as a matching problem where we want to pair students with seats to minimize the total distance traveled.

Consider what happens if we have students at positions [2, 7, 4] and seats at positions [3, 1, 5]. We need to decide which student should go to which seat.

If we assign randomly, we might get a suboptimal result. For example, if the student at position 2 goes to seat at position 5, and the student at position 7 goes to seat at position 1, we'd have large distances to cover.

The optimal strategy is to match students and seats based on their relative ordering. Think of it this way: if we line up all students from left to right by their positions, and do the same for seats, then the leftmost student should go to the leftmost seat, the second-leftmost student to the second-leftmost seat, and so on.

Why does this work? If we tried to "cross" assignments (having a student on the left go to a seat on the right while a student on the right goes to a seat on the left), the paths would intersect, creating unnecessary extra distance. By maintaining the relative order, we avoid these inefficient crossings.

Mathematically, after sorting both arrays, the optimal assignment pairs students[i] with seats[i] for all i. The total minimum moves is then: sum(|students[i] - seats[i]|) for all i from 0 to n-1.

This greedy approach works because each student-seat pairing is independent once we've determined the optimal matching order through sorting.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution implements the greedy matching strategy we identified through sorting both arrays and pairing them in order.

Step-by-step implementation:

1. Sort both arrays:
   • seats.sort() - arranges seats in ascending order by position
   • students.sort() - arranges students in ascending order by position
2. Calculate total moves:
   • Use zip(seats, students) to pair up the sorted arrays element by element
   • For each pair (a, b) where a is a seat position and b is a student position, calculate the distance |a - b|
   • Sum all these distances using sum(abs(a - b) for a, b in zip(seats, students))

Why this works:

After sorting, we have:

• Seats ordered: seat[0] ≤ seat[1] ≤ ... ≤ seat[n-1]
• Students ordered: student[0] ≤ student[1] ≤ ... ≤ student[n-1]

The algorithm assigns:

• The leftmost student → the leftmost seat
• The second leftmost student → the second leftmost seat
• And so on...

This ensures no "crossing" of paths which would increase the total distance unnecessarily.

Time Complexity: O(n log n) due to sorting both arrays Space Complexity: O(1) if we don't count the space used by sorting (typically O(log n) for the sorting algorithm's recursion stack)

The elegance of this solution lies in recognizing that sorting transforms the problem from a complex assignment problem into a simple pairing problem where we just match elements at the same indices.

Example Walkthrough

Let's walk through a small example with seats = [4, 1, 5, 9] and students = [1, 3, 2, 6].

Step 1: Sort both arrays

• Sorted seats: [1, 4, 5, 9]
• Sorted students: [1, 2, 3, 6]

Step 2: Pair up elements at the same indices

After sorting, we match:

• Student at position 1 → Seat at position 1
• Student at position 2 → Seat at position 4
• Student at position 3 → Seat at position 5
• Student at position 6 → Seat at position 9

Step 3: Calculate moves for each pairing

• Pairing 1: |1 - 1| = 0 moves
• Pairing 2: |2 - 4| = 2 moves
• Pairing 3: |3 - 5| = 2 moves
• Pairing 4: |6 - 9| = 3 moves

Step 4: Sum up total moves Total = 0 + 2 + 2 + 3 = 7 moves

Why this is optimal:

Consider if we tried a different assignment, like having the student at position 6 go to seat at position 1 instead. This would require 5 moves just for that one student, plus we'd need to reassign the student at position 1 elsewhere. Any "crossing" of assignments where a leftward student goes to a rightward seat (and vice versa) creates inefficiency.

By maintaining the relative order through sorting and pairing, we ensure each student travels the minimum necessary distance to reach an available seat without creating conflicts or unnecessary detours.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the arrays seats and students. This is because:

• Sorting the seats array takes O(n × log n) time
• Sorting the students array takes O(n × log n) time
• The zip and sum operations with the list comprehension take O(n) time to iterate through both arrays once
• Overall: O(n × log n) + O(n × log n) + O(n) = O(n × log n)

The space complexity is O(log n). This is because:

• Python's built-in sort() method uses Timsort algorithm, which requires O(log n) space for the recursion stack in the worst case
• The zip operation and generator expression in the sum function use O(1) additional space since they don't create intermediate lists
• Overall: O(log n) + O(1) = O(log n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Optimize Individual Assignments Without Sorting

A common mistake is trying to greedily match each student to their nearest available seat without first sorting both arrays. This approach seems intuitive but leads to suboptimal solutions.

Why this fails: Consider seats = [1, 4, 2] and students = [5, 2, 3]

• If we greedily assign student at position 5 to the nearest seat (4), we get: 5→4 (1 move)
• Then student at position 2 might go to seat 2: 2→2 (0 moves)
• Finally student at position 3 goes to remaining seat 1: 3→1 (2 moves)
• Total: 3 moves

But the optimal solution after sorting gives us 2 moves total.

Solution: Always sort both arrays first before making assignments.

2. Modifying Input Arrays Without Considering Side Effects

The solution sorts the input arrays in-place using .sort(). If the caller expects the original arrays to remain unchanged, this could cause bugs.

Solution: Create copies if needed:

seats_sorted = sorted(seats)
students_sorted = sorted(students)

3. Assuming Positions Are Unique

The problem explicitly states that multiple seats/students can start at the same position. Some might incorrectly assume unique positions and try to use set operations or dictionaries for matching.

Why this fails: If seats = [1, 1, 3] and students = [1, 2, 2], using sets would lose duplicates and make correct assignment impossible.

Solution: Maintain all duplicate positions by using lists and sorting, not sets.

4. Over-complicating with Assignment Algorithms

Some might recognize this as a bipartite matching problem and try to implement complex algorithms like the Hungarian algorithm or use dynamic programming.

Why this is unnecessary: While these approaches work, they have higher time complexity (O(n³) for Hungarian algorithm) compared to the simple O(n log n) sorting solution.

Solution: Recognize that when quantities are equal (n seats for n students), sorting naturally provides the optimal pairing.