Minimum Number of Moves to Seat Everyone

Easy

#1855Time: O(n! * n). There are `n!` permutations to generate. For each permutation, we iterate through the `n` students to calculate the cost. This is computationally very expensive.Space: O(n). The recursion depth is `n`, so the call stack uses `O(n)` space. The array is modified in-place.

Patterns

Greedy

Algorithms

Sorting Counting Sort

Data structures

Array

Prompt

There are n availabe seats and n students standing in a room. You are given an array seats of length n, where seats[i] is the position of the i^th seat. You are also given the array students of length n, where students[j] is the position of the j^th student.

You may perform the following move any number of times:

Increase or decrease the position of the i^th student by 1 (i.e., moving the i^th student from position x to x + 1 or x - 1)

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.

Example 1:

Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Explanation: 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
Explanation: 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
Explanation: 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible way to assign students to seats. It generates all permutations of the seat assignments, calculates the total moves for each assignment, and finds the minimum among them. This method is exhaustive and guarantees the correct result but is computationally infeasible for the given constraints.

Algorithm

Define a recursive function, say generatePermutations(index, currentSeats).
The base case for the recursion is when index reaches the length of the array. At this point, a full permutation is formed.
In the base case, calculate the total moves by summing abs(students[i] - currentSeats[i]) for all i. Update the global minimum if the current sum is smaller.
In the recursive step, iterate from index to the end of the array. For each element j, swap it with the element at index, make a recursive call for index + 1, and then swap back to backtrack.
The initial call would be generatePermutations(0, seats).

Walkthrough

The core idea is to try every single one-to-one mapping between students and seats. We can fix the order of students and generate all permutations of the seats array. For each permutation of seats, we pair the i-th student with the i-th seat in the permuted list and calculate the sum of absolute differences of their positions. We keep track of the minimum sum found across all permutations. This guarantees finding the optimal solution because it exhaustively checks all possibilities. The algorithm can be implemented using a recursive function that generates permutations.

1class Solution {2    int minMoves = Integer.MAX_VALUE;3 4    public int minMovesToSeat(int[] seats, int[] students) {5        permute(seats, 0, students);6        return minMoves;7    }8 9    private void permute(int[] seats, int start, int[] students) {10        if (start == seats.length) {11            int currentMoves = 0;12            for (int i = 0; i < seats.length; i++) {13                currentMoves += Math.abs(seats[i] - students[i]);14            }15            minMoves = Math.min(minMoves, currentMoves);16            return;17        }18 19        for (int i = start; i < seats.length; i++) {20            swap(seats, start, i);21            permute(seats, start + 1, students);22            swap(seats, start, i); // backtrack23        }24    }25 26    private void swap(int[] arr, int i, int j) {27        int temp = arr[i];28        arr[i] = arr[j];29        arr[j] = temp;30    }31}

Complexity

Time

O(n! * n). There are `n!` permutations to generate. For each permutation, we iterate through the `n` students to calculate the cost. This is computationally very expensive.

Space

O(n). The recursion depth is `n`, so the call stack uses `O(n)` space. The array is modified in-place.

Trade-offs

Pros

Guaranteed to find the correct answer by checking every possibility.
Conceptually simple to understand as it directly models the problem statement of finding the best pairing.

Cons

Extremely inefficient due to its factorial time complexity.
Will result in a 'Time Limit Exceeded' error on most platforms for constraints where n is larger than about 10 or 12.

A much more efficient approach is based on a greedy strategy. The intuition is that to minimize the total moves, we should avoid "crossing" assignments. This means the student at the smallest position should go to the seat at the smallest position, the second smallest to the second smallest, and so on. This can be achieved by sorting both arrays and then pairing corresponding elements.

Algorithm

Sort the seats array in non-decreasing order.
Sort the students array in non-decreasing order.
Initialize a variable totalMoves to 0.
Iterate from i = 0 to n-1, where n is the number of students/seats.
In each iteration, calculate the absolute difference between seats[i] and students[i] and add it to totalMoves.
After the loop, totalMoves will hold the minimum number of moves required.

Walkthrough

The problem can be solved by realizing that the optimal strategy is to match the i-th student in the sorted list of student positions to the i-th seat in the sorted list of seat positions. It can be proven that any "crossed" assignment (e.g., smaller student to larger seat and larger student to smaller seat) can be "uncrossed" to reduce or maintain the total number of moves. This logic extends to n students and seats, meaning the minimum total distance is achieved when the sorted student positions are matched with the sorted seat positions.

1import java.util.Arrays;2 3class Solution {4    public int minMovesToSeat(int[] seats, int[] students) {5        // Sort both the seats and students arrays6        Arrays.sort(seats);7        Arrays.sort(students);8        9        int totalMoves = 0;10        // Iterate through the sorted arrays and sum the absolute differences11        for (int i = 0; i < seats.length; i++) {12            totalMoves += Math.abs(seats[i] - students[i]);13        }14        15        return totalMoves;16    }17}

Complexity

Time

O(n log n). The dominant operation is sorting the two arrays, each of which takes `O(n log n)` time. The final loop to sum the differences takes `O(n)` time.

Space

O(log n) to O(n). This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of `O(log n)` for the recursion stack. In the worst case, it can be `O(n)`.

Trade-offs

Pros

Vastly more efficient than the brute-force approach.
Relatively simple to implement using standard library sorting functions.
Passes the given constraints with ease.

Cons

While efficient, it's not the absolute fastest for this specific problem's constraints, as a linear time solution exists.
The space complexity can be O(n) in the worst-case for some in-place sort implementations.

Given the constraint that student and seat positions are within a small range (1 to 100), we can optimize the sorting step. Instead of a comparison-based sort (O(n log n)), we can use a non-comparison-based sort like Counting Sort, which works in linear time. This is the most efficient approach for this problem.

Algorithm

Determine the maximum possible position value, k (which is 100 in this problem).
Create two frequency arrays, seatCounts and studentCounts, of size k+1, initialized to zeros.
Iterate through the seats array. For each seatPosition, increment seatCounts[seatPosition].
Iterate through the students array. For each studentPosition, increment studentCounts[studentPosition].
Initialize totalMoves = 0, seatPtr = 1, and studentPtr = 1.
Loop n times (for each of the n pairs to be matched):
- Move seatPtr forward until an available seat is found (i.e., seatCounts[seatPtr] > 0).
- Move studentPtr forward until an available student is found (i.e., studentCounts[studentPtr] > 0).
- A match is found. Add abs(seatPtr - studentPtr) to totalMoves.
- Decrement both seatCounts[seatPtr] and studentCounts[studentPtr] to mark them as used.

Walkthrough

This approach builds upon the same greedy insight as the previous one: the i-th smallest student position should be matched with the i-th smallest seat position. The optimization comes from how we find these sorted positions. Since the positions are limited to the range [1, 100], we can use counting arrays to find the frequency of each seat and student position. After counting, we can iterate through the positions from 1 to 100 with two pointers, one for seats and one for students, to match them in sorted order and calculate the moves without explicitly building the sorted arrays.

1class Solution {2    public int minMovesToSeat(int[] seats, int[] students) {3        int maxPos = 100;4        int[] seatCounts = new int[maxPos + 1];5        int[] studentCounts = new int[maxPos + 1];6 7        for (int pos : seats) {8            seatCounts[pos]++;9        }10        for (int pos : students) {11            studentCounts[pos]++;12        }13 14        int totalMoves = 0;15        int seatPtr = 1;16        int studentPtr = 1;17        int n = seats.length;18 19        for (int i = 0; i < n; i++) {20            // Find the next available seat21            while (seatCounts[seatPtr] == 0) {22                seatPtr++;23            }24            25            // Find the next available student26            while (studentCounts[studentPtr] == 0) {27                studentPtr++;28            }29            30            // Match them, calculate moves, and decrement counts31            totalMoves += Math.abs(seatPtr - studentPtr);32            seatCounts[seatPtr]--;33            studentCounts[studentPtr]--;34        }35 36        return totalMoves;37    }38}

Complexity

Time

O(n + k), where `n` is the number of students and `k` is the range of positions. Populating the count arrays takes `O(n)`. The matching loop runs `n` times, and the pointers traverse the range `k` once in total. Thus, the overall complexity is linear.

Space

O(k). We use two arrays of size `k+1` to store the counts, where `k` is the maximum position value (100). Since `k` is a constant, this can be considered O(1) space.

Trade-offs

Pros

Most efficient solution with linear time complexity.
Perfectly suited for the given constraints on the position values.

Cons

The space complexity depends on the range of position values (k). If k were very large, this approach would be less memory-efficient than comparison sorting.

Solutions

Solution

1class Solution {2public3  int minMovesToSeat(int[] seats, int[] students) {4    Arrays.sort(seats);5    Arrays.sort(students);6    int ans = 0;7    for (int i = 0; i < seats.length; ++i) {8      ans += Math.abs(seats[i] - students[i]);9    }10    return ans;11  }12}

1class Solution {2public:3  int minMovesToSeat(vector<int> &seats, vector<int> &students) {4    sort(seats.begin(), seats.end());5    sort(students.begin(), students.end());6    int ans = 0;7    for (int i = 0; i < seats.size(); ++i) {8      ans += abs(seats[i] - students[i]);9    }10    return ans;11  }12};

1class Solution:2    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int: seats . sort() students . sort() return sum(abs(a - b) for a, b in zip(seats, students))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int minMovesToSeat(int[] seats, int[] students) {4    Arrays.sort(seats);5    Arrays.sort(students);6    int ans = 0;7    for (int i = 0; i < seats.length; ++i) {8      ans += Math.abs(seats[i] - students[i]);9    }10    return ans;11  }12}

1class Solution {2public:3  int minMovesToSeat(vector<int> &seats, vector<int> &students) {4    sort(seats.begin(), seats.end());5    sort(students.begin(), students.end());6    int ans = 0;7    for (int i = 0; i < seats.size(); ++i) {8      ans += abs(seats[i] - students[i]);9    }10    return ans;11  }12};

1class Solution:2    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int: seats . sort() students . sort() return sum(abs(a - b) for a, b in zip(seats, students))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.