Minimum Number of Moves to Seat Everyone

Easy · Greedy · Explanation and code example

Counting Sort (Optimal)

How it works

When multiple students are at the same position or multiple seats are at the same position, we can batch process them. Instead of matching one pair at a time, we match min(count_seats[i], count_students[j]) pairs at once, multiplying the distance by the batch size.

This optimization reduces iterations when there are many duplicates, though the asymptotic complexity remains the same.

Steps

  1. Create count arrays for seats and students.
  2. Use two pointers i and j starting at position 0.
  3. While unmatched pairs remain:
    • Advance i until count_seats[i] > 0.
    • Advance j until count_students[j] > 0.
    • Compute tmp = min(count_seats[i], count_students[j]).
    • Add |i - j| * tmp to res, decrement counts by tmp.
  4. Return the total.

Complexity

  • Time complexity: O(n + m1 + m2)
  • Space complexity: O(m1 + m2)

Where n is the size of the input arrays, m1 is the maximum value in the array seats, and m2 is the maximum value in the array students.

Things to watch for

Not Sorting Both Arrays

The greedy solution requires sorting both the seats and students arrays before pairing. Sorting only one array or forgetting to sort altogether will produce incorrect results. The optimal pairing matches the i-th smallest student with the i-th smallest seat, which requires both arrays to be in sorted order.

Using Signed Subtraction Instead of Absolute Difference

When calculating the distance between a seat and a student, you must use abs(seats[i] - students[i]), not just seats[i] - students[i]. If a student is at a larger position than their assigned seat, the subtraction would be negative, leading to an incorrect (and possibly negative) total. Always use the absolute value to measure distance.

Python code example

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        count_seats = [0] * (max(seats) + 1)
        count_students = [0] * (max(students) + 1)

        def count_sort(arr, count):
            for num in arr:
                count[num] += 1

        count_sort(seats, count_seats)
        count_sort(students, count_students)

        remain = len(seats)
        i = j = res = 0
        while remain:
            if count_seats[i] == 0:
                i += 1
            if count_students[j] == 0:
                j += 1
            if count_seats[i] and count_students[j]:
                tmp = min(count_seats[i], count_students[j])
                res += abs(i - j) * tmp
                count_seats[i] -= tmp
                count_students[j] -= tmp
                remain -= tmp
        return res

C++ code example

class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students) {
        int maxSeat = *max_element(seats.begin(), seats.end());
        int maxStudent = *max_element(students.begin(), students.end());

        vector<int> count_seats(maxSeat + 1, 0);
        vector<int> count_students(maxStudent + 1, 0);

        for (int s : seats) count_seats[s]++;
        for (int s : students) count_students[s]++;

        int remain = seats.size(), i = 0, j = 0, res = 0;
        while (remain > 0) {
            if (count_seats[i] == 0) {
                i++;
                continue;
            }
            if (count_students[j] == 0) {
                j++;
                continue;
            }
            int tmp = min(count_seats[i], count_students[j]);
            res += abs(i - j) * tmp;
            count_seats[i] -= tmp;
            count_students[j] -= tmp;
            remain -= tmp;
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations