Height Checker
Problem
Students must stand in non-decreasing order of height. Given the current line in heights, return the number of indices where heights[i] differs from the sorted order (the "expected" line).
heights = [1, 1, 4, 2, 1, 3]3def height_checker(heights):
expected = sorted(heights)
count = 0
for i in range(len(heights)):
if heights[i] != expected[i]:
count += 1
return countfunction heightChecker(heights) {
const expected = heights.slice().sort((a, b) => a - b);
let count = 0;
for (let i = 0; i < heights.length; i++) {
if (heights[i] !== expected[i]) count++;
}
return count;
}class Solution {
public int heightChecker(int[] heights) {
int[] expected = heights.clone();
Arrays.sort(expected);
int count = 0;
for (int i = 0; i < heights.length; i++) {
if (heights[i] != expected[i]) count++;
}
return count;
}
}int heightChecker(vector<int>& heights) {
vector<int> expected = heights;
sort(expected.begin(), expected.end());
int count = 0;
for (int i = 0; i < (int)heights.size(); i++) {
if (heights[i] != expected[i]) count++;
}
return count;
}Explanation
The students should be lined up in non-decreasing height order. The question is simply how many of them are currently standing in the wrong spot compared to that ideal lineup.
The straightforward idea is exactly the solution: build the expected lineup by sorting a copy of heights, then compare position by position. Sorting a copy (not the original) is important so we still know who is actually standing where.
We walk through every index i and check whether heights[i] matches expected[i]. Each mismatch means that student is out of place, so we add 1 to count. At the end count is the answer.
Example: heights = [1, 1, 4, 2, 1, 3] sorts to expected = [1, 1, 1, 2, 3, 4]. Comparing them, indices 2, 4, and 5 differ (4 vs 1, 1 vs 3, 3 vs 4), so the answer is 3.
The cost is dominated by the sort, and the comparison pass is a single linear scan.