Minimum Number of Moves to Seat Everyone

Difficulty: Easy | Acceptance: 87.20% | Paid: No Topics: Array, Greedy, Sorting, Counting Sort

There are n seats and n students. You are given an array seats of length n, where seats[i] is the position of the ith seat, and an array students of length n, where students[j] is the position of the jth student.

You may move the students any number of times (i.e., move each student from x to y at a cost of |x - y|). 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.

• Examples
• Constraints
• Sorting Approach
• Counting Sort Approach

Examples

Example 1

Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Explanation: Move students:
- Move student 1 from 2 to 1 (1 move)
- Move student 2 from 7 to 5 (2 moves)
- Move student 3 from 4 to 3 (1 move)
Total moves: 1 + 2 + 1 = 4

Example 2

Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Explanation: The students are moved as follows:
- The student at position 1 is moved to seat 1 (0 moves)
- The student at position 2 is moved to seat 4 (2 moves)
- The student at position 3 is moved to seat 5 (2 moves)
- The student at position 6 is moved to seat 9 (3 moves)
Total moves: 0 + 2 + 2 + 3 = 7

Example 3

Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Explanation: The students are moved as follows:
- The student at position 1 is moved to seat 2 (1 move)
- The student at position 2 is moved to seat 2 (0 moves)
- The student at position 3 is moved to seat 6 (3 moves)
- The student at position 6 is moved to seat 6 (0 moves)
Total moves: 1 + 0 + 3 + 0 = 4

Constraints

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

Sorting Approach

Intuition To minimize total moves, match the closest student to each seat. Sorting both arrays and pairing elements at the same index achieves this optimal matching.

Steps

• Sort the seats array in ascending order
• Sort the students array in ascending order
• Sum the absolute differences between corresponding elements at each index

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        return sum(abs(seats[i] - students[i]) for i in range(len(seats)))

Complexity

• Time: O(n log n) for sorting
• Space: O(1) or O(n) depending on the sorting algorithm
• Notes: Simple and intuitive approach with good performance for typical input sizes

Counting Sort Approach

Intuition Since positions are bounded (1 to 100), we can use counting sort to efficiently match students to seats without full sorting, achieving linear time complexity.

Steps

• Create count arrays for seats and students of size 101
• Count the frequency of each position for both arrays
• Iterate through positions 1 to 100
• For each position, match available students to available seats
• Calculate total moves by multiplying the position difference by the number of matches

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seat_count = [0] * 101
        student_count = [0] * 101
        
        for seat in seats:
            seat_count[seat] += 1
        
        for student in students:
            student_count[student] += 1
        
        moves = 0
        i = j = 1
        while i <= 100 and j <= 100:
            while i <= 100 and seat_count[i] == 0:
                i += 1
            while j <= 100 and student_count[j] == 0:
                j += 1
            
            if i <= 100 and j <= 100:
                min_count = min(seat_count[i], student_count[j])
                moves += min_count * abs(i - j)
                seat_count[i] -= min_count
                student_count[j] -= min_count
        
        return moves

Complexity

• Time: O(n + k) where k = 100 (the range of positions)
• Space: O(k) for the count arrays
• Notes: More efficient for large n due to linear time complexity, but uses extra space