height-checker-counting-sort

Height Checker (LeetCode 1051): Counting Sort Beats Sorting

Height Checker gives you the students' heights in their current order and asks how many positions differ from the order you'd get after sorting by height. It is an easy problem, but it is a nice place to show you know when a counting sort applies.

Baseline: sort and compare

def height_checker(heights):

expected = sorted(heights)

return sum(a != b for a, b in zip(heights, expected))

That is O(n log n). Good enough, and worth writing first.

Counting sort: O(n + k)

Heights are limited to 1..100, so count how many students have each height, then walk the counts to rebuild the expected order on the fly and compare as you go. No sorted copy is needed.

def height_checker(heights):

count = [0] * 101

for h in heights:

count[h] += 1

mismatches, cur = 0, 1

for h in heights:

while count[cur] == 0:

cur += 1

if h != cur:

mismatches += 1

count[cur] -= 1

return mismatches

print(height_checker([1, 1, 4, 2, 1, 3])) # 3

Talking points

Say why counting sort is legal here: the value range is small and fixed, so k = 100 is a constant. Mention the trade-off if the range were huge (fall back to sorting). Interviewers like hearing that you read the constraints before choosing an algorithm.

Disclosure: I'm on the team behind Linkjob.ai, a tool that gives real-time hints while you practice coding interviews.

Made on mmm