Height Checker
Easy · Arrays & Hashing · Array · Sorting · Counting Sort
Problem
Students are lining up for a photo, which needs them in non-decreasing order of height. Let expected be the heights in that required order.
You are given heights, the order the students are actually standing in. Return the number of indices i where heights[i] != expected[i].
Examples
Input: heights = [3,1,2,2] Output: 3
expected is [1,2,2,3]. Positions 0, 1 and 3 differ; position 2 already holds a 2.
Input: heights = [4,4,4] Output: 0
The line is already in order.
Input: heights = [5,4,3,2,1] Output: 4
expected is [1,2,3,4,5]. Only the middle student, height 3, is in the right place.
Constraints
- 1 <= len(heights) <= 100
- 1 <= heights[i] <= 100
Approaches
- Baseline: sort a copy and compare — time O(n log n), space O(n)
Follow-up
A related question is how few students must move to fix the line. That is not this count: it is the length of the line minus its longest non-decreasing subsequence, because the students in that subsequence can stay while everyone else is reinserted.
Related problems
Start free on Cariara · Coding problems · System design studio
