Python 2037.py
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
seats .sort()
students.sort()
result = 0
for i, j in zip(seats, students):
result += abs(i - j)
return result
Difficulty
and has an acceptance rate of about 87% (300k+ submissions).
Typical patterns to solve this problem:
- Array
- Counting Sort
- Greedy
- Sorting
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a single method minMovesToSeat. The method receives two integer lists, seats and students, and computes the minimum total number of moves required to seat every student. A move is defined as the absolute distance a student must travel to reach a seat. The algorithm works by first sorting both input lists, then pairing each seat with the corresponding student in order, and finally accumulating the absolute differences of each pair.
Key Steps
The first step prepares the data for optimal pairing by arranging both lists in non-decreasing order.
seats.sort()
students.sort()
Sorting guarantees that the smallest seat index aligns with the smallest student index, the second smallest with the second smallest, and so on. This ordering is essential for achieving the minimal total distance.
The second step initializes an accumulator that will hold the running total of moves.
result = 0
The core of the algorithm iterates over the paired elements of the sorted lists. The zip function creates tuples containing one seat and one student at each position. For each pair, the absolute difference is calculated and added to the accumulator.
for i, j in zip(seats, students):
result += abs(i - j)
Finally, the method returns the accumulated value, representing the minimal total number of moves.
return result
Edge Cases Handled
When both input lists are empty, the sorting operations are no-ops, the loop body never executes, and the accumulator remains zero, which correctly reflects that no moves are needed. If the lists contain a single element each, the algorithm still sorts (a trivial operation) and computes the absolute difference of the sole pair, delivering the correct result for that minimal scenario. The use of abs ensures that the calculation works regardless of whether a student index is larger or smaller than the corresponding seat index, covering cases where students start to the left or right of their assigned seats.
Performance Optimizations
The implementation leverages in-place sorting (list.sort()) rather than creating new sorted copies, which reduces memory overhead. By iterating with zip, the code processes both lists simultaneously without the need for additional indexing variables or manual bounds checking. The accumulation of the result uses a simple integer addition inside the loop, avoiding any unnecessary data structures or function calls beyond the built-in abs. These choices keep the execution path tight and minimize the amount of work performed per element.
ELI5 - Simplified Explanation
Imagine there are some chairs lined up in a room and a bunch of children waiting to find a place to sit. Each chair has a number and each child has a number too. To make things fair and keep the children as close to their favorite spots as possible, the seats and the children are both put in order from the smallest number to the biggest number.
Once everything is lined up, each child walks to the chair that is in the same position as them in the line. Because some children might be a little bit further away from their chair than others, it is necessary to see how much space is between them. The code looks at each pair of a child and a chair and subtracts one number from the other to see the distance. Since distance cannot be negative, it just takes the total amount of steps needed for everyone to reach a seat. This happens over and over until every single child is sitting down comfortably in a chair.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | Python | Java | ||||||||
| leetcode.ca | C++ | Python | Java | Go | C | Rust | TS | ||||
| Progiez | C++ | Python | Java | ||||||||
| github | black-shadows | C++ | |||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JS | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C, C++, Go, Java, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java |
Videos
Solved On The Same Day
- problem 1952: Three Divisors
- problem 2016: Maximum Difference Between Increasing Elements
- problem 2027: Minimum Moves to Convert String
- problem 2350: Shortest Impossible Sequence of Rolls
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality