The problem. Students stand in a line; heights[i] is the height of the student at position i. The line should be in non-decreasing order of height. Return how many positions have the wrong student — where heights[i] differs from the sorted line's value at i.
heights = [1, 1, 4, 2, 1, 3] -> 3
heights = [5, 1, 2, 3, 4] -> 5
heights = [1, 2, 3, 4, 5] -> 0Comparison sorting costs O(n log n). Two common situations do better. When the values come from a small range — heights up to 100, digits, letters, colours — you can count how many of each there are, and the counts are the sorted order: a counting sort, O(n + k). And when you only need to split values into two or three groups — evens and odds, below and above a pivot, 0s/1s/2s — a single partition pass with two pointers puts every value in its group in O(n), in place.
This chapter covers both: Height Checker counts, Sort Array By Parity partitions, and Maximum Gap uses buckets to find a sorted-order fact without fully sorting.
function heightChecker(heights) { const expected = [...heights].sort((a, b) => a - b); let mismatches = 0; for (let i = 0; i < heights.length; i++) { if (heights[i] !== expected[i]) mismatches++; } return mismatches;}Time O(n log n), space O(n). Perfectly good — and the honest first answer.
Count each height, then read the sorted line off the counts while walking the real line.
function heightChecker(heights) { const count = new Array(101).fill(0); for (const h of heights) count[h]++; // heights are 1..100 let mismatches = 0, h = 1; for (const actual of heights) { while (count[h] === 0) h++; // the next height in sorted order if (actual !== h) mismatches++; count[h]--; } return mismatches;}Time O(n + k), space O(k) for heights up to k = 100. The sorted line is never built: the counts are read off one value at a time, and h only ever moves forward.
[5, 1, 2, 3, 4] gives 5.