2037. Minimum Number of Moves to Seat Everyone
Problem Description
In this problem, we have n
seats and n
students, with each being given an initial position. The goal is to find the minimum number of moves required to place each student in a seat such that no two students end up in the same seat. The array seats
contains the positions of the seats and the array students
contains the initial positions of the students. A move consists of increasing or decreasing the position of a student by 1. This problem becomes a matter of optimally matching each student to a seat.
Intuition
The key to solving this problem is realizing that the most optimal way to match students to seats with the minimum moves is to match the closest available seat to each student. To achieve this, we can sort both the seats
and students
arrays. Sorting brings pairs of students and seats that are closest to each other in correspondence.
Once sorted, the position of the i-th student should match with the i-th seat. Since each move changes a position by 1, the total moves for each student to reach their seat is the absolute difference between their position and their allocated seat's position. By sorting, we ensure that we are not crossing pairs, which could potentially lead to a higher number of moves if we were to move students past each other.
When the pairs are matched one-to-one in a sorted manner, we can sum the absolute differences of corresponding pairs to find the minimum number of moves required for all students to be seated.
Learn more about Sorting patterns.
Solution Approach
The solution involves sorting algorithms and the concept of absolute difference to calculate the minimum number of moves. The following steps depict the implementation:
-
Sorting: We use a sorting algorithm (such as quicksort, mergesort, etc., typically
O(n log n)
complexity) to sort both theseats
andstudents
arrays. In Python, this is done using thesort()
method directly on the lists, which sorts the list in-place. -
Pairing Students with Seats: After sorting, the students and seats are paired up by their indices. That is, the first student (
students[0]
) will go to the first seat (seats[0]
), and so on. -
Calculating Moves: Since the solution only requires the total number of moves, we go through each pair
(student, seat)
and calculate the absolute difference between their positions. Theabs()
function is used for this purpose, which is a built-in function in Python to calculate the absolute value of a number.For example, if a student is at position 2 (
students[i] = 2
) and their paired seat is at position 5 (seats[i] = 5
), the moves required to get the student to that seat would beabs(2 - 5) = 3
. The number of moves is then added to a running total. -
Summing Up Moves: As we calculate the absolute difference for each student and seat pair, we sum up these differences using the
sum()
function. This sum represents the total minimum number of moves required to seat all students. Thezip()
function in Python is helpful here to iterate over corresponding elements ofseats
andstudents
simultaneously.
The code for this would look like this:
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
seats.sort() # Sort the seats array.
students.sort() # Sort the students array.
# Calculate the sum of absolute differences between paired students and seats.
return sum(abs(a - b) for a, b in zip(seats, students))
This approach guarantees an optimal solution with a time complexity of O(n log n)
because of the sorting step, which is the most time-consuming part of the algorithm. The pairing and summing steps are linear, making it O(n)
. Therefore, the sorting step dictates the overall time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example with n = 3
seats and n = 3
students with the following initial positions:
seats = [4, 1, 5]
students = [3, 2, 6]
First, using the solution approach, we need to sort both seats
and students
arrays to organize them in ascending order:
- Sorted
seats
:[1, 4, 5]
- Sorted
students
:[2, 3, 6]
Now, we pair the students with their seats by index:
- 1st pair: seat at position 1 and student at position 2 (student needs to move 1 position to the left)
- 2nd pair: seat at position 4 and student at position 3 (student needs to move 1 position to the right)
- 3rd pair: seat at position 5 and student at position 6 (student needs to move 1 position to the left)
Next, we calculate the absolute differences for each pair to find out the number of moves required:
- Moves for 1st pair:
abs(seats[0] - students[0]) = abs(1 - 2) = 1
- Moves for 2nd pair:
abs(seats[1] - students[1]) = abs(4 - 3) = 1
- Moves for 3rd pair:
abs(seats[2] - students[2]) = abs(5 - 6) = 1
Finally, we sum up the number of moves for all pairs to find the total minimum number of moves:
- Total moves:
(1 + 1 + 1) = 3
Thus, it takes a minimum of 3 moves to seat all the students.
Solution Implementation
1class Solution:
2 def min_moves_to_seat(self, seats: List[int], students: List[int]) -> int:
3 # First, sort the lists of seats and students to organize them in ascending order.
4 # This aligns each student to the closest available seat.
5 seats.sort()
6 students.sort()
7
8 # Next, calculate the total number of moves by iterating over the paired sorted lists.
9 # For each pair, find the absolute difference between a student's position and
10 # a seat's position. This represents the number of moves a student must make to reach the seat.
11 moves = sum(abs(seat - student) for seat, student in zip(seats, students))
12
13 # Return the total number of moves needed for all students to sit in the seats.
14 return moves
15
1import java.util.Arrays; // Import Arrays class for sorting
2
3class Solution {
4 // Method to find the minimum number of moves required to seat all students.
5 // Each student moves to a seat, and the total moves should be minimized.
6 public int minMovesToSeat(int[] seats, int[] students) {
7 // Sort the arrays to match student-seat pairs by their order.
8 Arrays.sort(seats);
9 Arrays.sort(students);
10
11 // Initialize the count of moves to zero.
12 int totalMoves = 0;
13
14 // Iterate over the arrays to match each student to a seat
15 for (int i = 0; i < seats.length; ++i) {
16 // Add the absolute difference of positions to total moves.
17 // Absolute difference indicates the number of moves for each student.
18 totalMoves += Math.abs(seats[i] - students[i]);
19 }
20
21 // Return the total number of moves required to seat all students.
22 return totalMoves;
23 }
24}
25
1#include <vector> // Include header for vector
2#include <algorithm> // Include header for sort
3
4class Solution {
5public:
6 // Function to find the minimum number of moves to seat everyone
7 int minMovesToSeat(vector<int>& seats, vector<int>& students) {
8 // Sort the 'seats' vector in non-decreasing order.
9 sort(seats.begin(), seats.end());
10 // Sort the 'students' vector in non-decreasing order.
11 sort(students.begin(), students.end());
12
13 // Initialize a variable 'minMoves' to store the minimum number of moves needed.
14 int minMoves = 0;
15 // Iterate over the sorted vectors to find the total moves needed.
16 for (int i = 0; i < seats.size(); ++i) {
17 // Calculate the absolute difference between corresponding seats and students
18 // and add it to the 'minMoves' counter.
19 minMoves += abs(seats[i] - students[i]);
20 }
21 // Return the total minimum number of moves required.
22 return minMoves;
23 }
24};
25
1// Function to calculate the minimum number of moves required to seat students.
2// Each student moves to their seat with the least possible amount of individual moves.
3// Parameters `seats` and `students` are arrays of numbers representing seat positions and students' current positions respectively.
4function minMovesToSeat(seats: number[], students: number[]): number {
5 // Sort the seats array in ascending order.
6 seats.sort((a, b) => a - b);
7 // Sort the students array in ascending order.
8 students.sort((a, b) => a - b);
9
10 // Length of the seats array, which is also the number of students.
11 const numberOfSeats = seats.length;
12 // Initialize the accumulator for the total moves required.
13 let totalMoves = 0;
14
15 // Iterate over each seat/student pair to calculate the total moves.
16 for (let index = 0; index < numberOfSeats; index++) {
17 // Increase the total moves by the distance the current student needs to move to reach the current seat.
18 totalMoves += Math.abs(seats[index] - students[index]);
19 }
20
21 // Return the computed total moves.
22 return totalMoves;
23}
24
Time and Space Complexity
The given code sorts two lists, calculates the absolute difference between corresponding elements from each sorted list, and then sums the differences.
Time Complexity:
-
Sorting both
seats
andstudents
arrays has a time complexity ofO(n log n)
wheren
is the number of elements in each list. Since both lists are sorted independently, the combined time complexity isO(2 * n log n)
which simplifies toO(n log n)
. -
The
zip()
function pairs the elements of both lists, which isO(n)
wheren
is the length of the shorter list. Here we can assume both lists are the same length. -
The list comprehension with
sum()
iterates over the zipped lists to compute the absolute differences and sum them up. This operation is linear with respect to the number of seats/students, so it isO(n)
.
Thus, the overall time complexity of the provided code is O(n log n) + O(n)
. Since O(n log n)
dominates O(n)
, the final time complexity is O(n log n)
.
Space Complexity:
-
The sorting is done in-place, so it doesn't require additional space proportional to the input size. Thus, the space complexity of the sorting operation is
O(1)
. -
The use of
zip()
and the list comprehension withinsum()
does not create a new list of sizen
but instead creates an iterator that generates tuples one by one. Therefore, it only requires constant extra space. -
The final expression computes the sum in constant space, adding the absolute difference one pair at a time.
So, the overall space complexity of the provided code is O(1)
, constant space, since it only uses a fixed amount of additional memory aside from the input lists.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!