Python 1051.py
class Solution:
def heightChecker(self, heights: List[int]) -> int:
return sum( h != e for h, e in zip(heights, sorted(heights)) )
Difficulty
and has an acceptance rate of about 82% (800k+ submissions).
Typical patterns to solve this problem:
- Array
- Counting Sort
- 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 heightChecker. The method receives a list of integers representing heights and returns the count of positions where the current ordering differs from the sorted ordering. The solution is concise, leveraging Python’s built-in functions to achieve the required result in a single expression.
Key Steps
Sorting the Input
The first logical operation is the creation of a sorted version of the input list.
sorted_heights = sorted(heights)
sorted returns a new list arranged in non-decreasing order. This step establishes the reference ordering against which the original list will be compared.
Pairwise Comparison
The method then pairs each element of the original list with the corresponding element of the sorted list using zip.
pairs = zip(heights, sorted_heights)
Each pair (h, e) consists of the height at a particular index in the original list (h) and the height that should appear at that index in a correctly ordered list (e).
Detecting Mismatches
For every pair, a boolean expression evaluates whether the two values differ.
mismatch = h != e
In Python, True evaluates to 1 and False to 0. This property enables the direct accumulation of mismatches.
Summation of Mismatches
The generator expression that yields the boolean results is passed directly to sum, which aggregates the total number of mismatched positions.
result = sum(h != e for h, e in zip(heights, sorted(heights)))
The final integer returned by the method represents the number of students standing in the wrong position.
Edge Cases Handled
When the input list is empty, sorted(heights) also yields an empty list. zip produces no pairs, and the generator expression yields no values, causing sum to return 0. This correctly indicates that no mismatches exist.
If the list contains a single element, the sorted version is identical to the original. The comparison h != e evaluates to False, and the sum remains 0, reflecting the absence of any discrepancy.
For lists that are already sorted, every comparison yields False, and the method returns 0. Conversely, for a list sorted in reverse order, each position differs from the sorted reference, and the sum equals the length of the list, accurately counting all mismatches.
When duplicate heights appear, the sorting process preserves the relative order of equal elements as defined by the stable sorting algorithm. The pairwise comparison still correctly identifies positions where a duplicate value is out of place relative to the stable sorted order.
Performance Optimizations
The implementation benefits from several built-in efficiencies. The sorted function employs Timsort, a hybrid stable sorting algorithm optimized for real-world data patterns, delivering fast sorting without additional code overhead. By using a generator expression inside sum, the code avoids constructing an intermediate list of boolean values, thereby reducing memory pressure and enabling lazy evaluation. The direct use of boolean-to-integer conversion eliminates the need for explicit conditional counting logic, streamlining the computation into a single pass over the zipped pairs. These choices collectively produce a compact and efficient solution.
ELI5 - Simplified Explanation
Imagine a row of children standing in line, but they are all mixed up and not in order of how tall they are. This code first takes that line and makes a perfect, tidy copy where all the children are standing exactly from shortest to tallest. Then it looks at the original messy line and walks down it, comparing each child to the child standing in the same spot in the tidy copy. Every time it finds a child who is not in the spot where they belong, it marks them down. By the end, it counts up all the spots that had the wrong person in them so that you know how many children were standing in the wrong place.
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 | TS | |||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| Progiez | C++ | Python | Java | |||||||
| github | BigEggStudy | C# | ||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| DimitrisJim | C | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| Garvit244 | Python | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| shreymehul | C# | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| DimitrisJim | C | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| Garvit244 | Python | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| shreymehul | C# | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java |
Videos
Solved On The Same Day
- problem 1046: Last Stone Weight
- problem 779: K-th Symbol in Grammar
- problem 855: Exam Room
- problem 955: Delete Columns to Make Sorted II
- problem 957: Prison Cells After N Days
- problem 1052: Grumpy Bookstore Owner
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