# Minimum Number of Moves to Seat Everyone
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-moves-to-seat-everyone
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array
---
## Problem
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 `ith` seat. You are also given the array `students` of length `n`, where `students[j]` is the position of the `jth` student.

You may perform the following move any number of times:

* Increase or decrease the position of the `ith` student by `1` (i.e., moving the `ith` 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
## Brute-Force with Permutations
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    int minMoves = Integer.MAX_VALUE;

    public int minMovesToSeat(int[] seats, int[] students) {
        permute(seats, 0, students);
        return minMoves;
    }

    private void permute(int[] seats, int start, int[] students) {
        if (start == seats.length) {
            int currentMoves = 0;
            for (int i = 0; i < seats.length; i++) {
                currentMoves += Math.abs(seats[i] - students[i]);
            }
            minMoves = Math.min(minMoves, currentMoves);
            return;
        }

        for (int i = start; i < seats.length; i++) {
            swap(seats, start, i);
            permute(seats, start + 1, students);
            swap(seats, start, i); // backtrack
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```
### 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)`.

## Greedy Approach with Sorting
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.
**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)`.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        // Sort both the seats and students arrays
        Arrays.sort(seats);
        Arrays.sort(students);
        
        int totalMoves = 0;
        // Iterate through the sorted arrays and sum the absolute differences
        for (int i = 0; i < seats.length; i++) {
            totalMoves += Math.abs(seats[i] - students[i]);
        }
        
        return totalMoves;
    }
}
```
### 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.

## Optimal Approach with Counting Sort
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        int maxPos = 100;
        int[] seatCounts = new int[maxPos + 1];
        int[] studentCounts = new int[maxPos + 1];

        for (int pos : seats) {
            seatCounts[pos]++;
        }
        for (int pos : students) {
            studentCounts[pos]++;
        }

        int totalMoves = 0;
        int seatPtr = 1;
        int studentPtr = 1;
        int n = seats.length;

        for (int i = 0; i < n; i++) {
            // Find the next available seat
            while (seatCounts[seatPtr] == 0) {
                seatPtr++;
            }
            
            // Find the next available student
            while (studentCounts[studentPtr] == 0) {
                studentPtr++;
            }
            
            // Match them, calculate moves, and decrement counts
            totalMoves += Math.abs(seatPtr - studentPtr);
            seatCounts[seatPtr]--;
            studentCounts[studentPtr]--;
        }

        return totalMoves;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  int minMovesToSeat(int[] seats, int[] students) {
    Arrays.sort(seats);
    Arrays.sort(students);
    int ans = 0;
    for (int i = 0; i < seats.length; ++i) {
      ans += Math.abs(seats[i] - students[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMovesToSeat(vector<int> &seats, vector<int> &students) {
    sort(seats.begin(), seats.end());
    sort(students.begin(), students.end());
    int ans = 0;
    for (int i = 0; i < seats.size(); ++i) {
      ans += abs(seats[i] - students[i]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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))

```