Height Checker — Solution in Python, Java & C++
Height Checker solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and sorting.
Height Checker is an easy coding problem on arrays, sorting and counting sort, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Counting Sort
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A school is taking an annual photo of all the students, who should stand in non-decreasing order of height. Let expected be that correctly ordered line.
Given the current line heights, return the number of positions where heights[i] != expected[i].
Example 1
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: expected = [1,1,1,2,3,4]; indices 2, 4 and 5 differ.
Example 2
Input: heights = [5,1,2,3,4]
Output: 5
Example 3
Input: heights = [1,2,3,4,5]
Output: 0
Constraints
1 <= heights.length <= 401 <= heights[i] <= 100
Hints for Height Checker
Hint 1
Sort a copy — the original order is what you are comparing against.
Hint 2
Then count positions where the two arrays disagree.
Hint 3
Heights are bounded by 100, so a counting sort makes it O(n + 100).
How to solve Height Checker
Sort a copy to get the expected line and count positions that disagree with the original.
Approach
- Sort a copy of
heights. - Count indices
iwithheights[i] != expected[i].
Why it works
The expected line is by definition the sorted order; comparing index by index counts exactly the students standing in the wrong slot.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Heights are ≤ 100, so a counting sort makes this
O(n + 100). - Sorting in place destroys the original you must compare against.
Reference solution
Python
def heightChecker(heights):
expected = sorted(heights)
return sum(1 for i in range(len(heights)) if heights[i] != expected[i])Java
public static int heightChecker(int[] heights) {
int[] expected = Arrays.copyOf(heights, heights.length);
Arrays.sort(expected);
int count = 0;
for (int i = 0; i < heights.length; i++) {
if (heights[i] != expected[i]) count++;
}
return count;
}C++
int heightChecker(vector<int>& heights) {
vector<int> expected = heights;
sort(expected.begin(), expected.end());
int count = 0;
for (size_t i = 0; i < heights.size(); i++) {
if (heights[i] != expected[i]) count++;
}
return count;
}JavaScript
var heightChecker = function(heights) {
const expected = heights.slice().sort(function(a, b) { return a - b; });
let count = 0;
for (let i = 0; i < heights.length; i++) {
if (heights[i] !== expected[i]) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms