Students Out of Line
Problem
For a class photo, students should stand in non-decreasing order of height. The photographer gets the current line as heights (in centimetres).
Return how many positions hold a student whose height differs from the height that belongs at that position in the correctly sorted line.
Example 1
- Input:
- heights = [150, 142, 160, 150, 171]
- Output:
- 4
The sorted line is [142, 150, 150, 160, 171]; positions 0 to 3 differ (150 vs 142, 142 vs 150, 160 vs 150, 150 vs 160) and only the last student is in place.
Example 2
- Input:
- heights = [120, 130, 140]
- Output:
- 0
Constraints
- 1 ≤ heights.length ≤ 10^5
- 100 ≤ heights[i] ≤ 220
Hint
Show the first hint
You need the sorted line to compare against. How cheaply can you build it here?
Walkthrough
How to approach it
01Clarify before coding
- Do equal heights count as mismatches when swapped? No: we compare heights, not identities.
- Is the range always 100..220? Yes, which makes counting sort a natural fit.
02Brute force
Sort a copy with a comparison sort and count positions where the copy and the original differ.
Cost: O(n log n) time, O(n) space. Fine, but the small height range allows linear time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.