#1051
Height Checker
Easy Counting sort
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Students stand in a line. Count how many positions differ from where they'd be if the line were sorted by height (heights are 1..100).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many students stand in the wrong place compared with the sorted line?
Why this works: heights are only 1..100, so counting sort gives the expected order in O(n).
Example: [1, 1, 4, 2, 1, 3] → expected [1, 1, 1, 2, 3, 4]
differences at indexes 2, 4, 5 → 3✦Hints open one at a time
Compare the array with its sorted copy.
With heights only up to 100, counting sort builds the sorted order in O(n).
↗Approach
Count each height, then walk heights from 1 to 100 producing the expected order on the fly, comparing with the actual line.
</>Solution (Java)
class Solution {
public int heightChecker(int[] heights) {
int[] count = new int[101];
for (int h : heights) count[h]++;
int mismatches = 0, h = 1;
for (int actual : heights) {
while (count[h] == 0) h++; // next height in sorted order
if (actual != h) mismatches++;
count[h]--;
}
return mismatches;
}
}!Common mistake
Sorting the original array in place and then comparing it with itself.
Complexity
- Time: O(n + 100).
- Space: O(100).
Topic: Sorting
🎬 Episodes 24–28: video coming soon