This problem asks for the number of positions where the current heights differ from the sorted expected order. Build a sorted version of the heights array, then iterate to count mismatches. Efficient solutions often leverage counting sort for small-range integer heights.
Problem Statement
A school wants to photograph students standing in a single file line in non-decreasing height order. You are given an integer array heights representing the current order of students, where heights[i] is the height of the ith student.
Return the number of indices where the current arrangement does not match the expected sorted order. For example, if a student is taller or shorter than the expected height at the same position, it counts as a mismatch.
Examples
Example 1
Input: heights = [1,1,4,2,1,3]
Output: 3
heights: [1,1,4,2,1,3] expected: [1,1,1,2,3,4] Indices 2, 4, and 5 do not match.
Example 2
Input: heights = [5,1,2,3,4]
Output: 5
heights: [5,1,2,3,4] expected: [1,2,3,4,5] All indices do not match.
Example 3
Input: heights = [1,2,3,4,5]
Output: 0
heights: [1,2,3,4,5] expected: [1,2,3,4,5] All indices match.
Constraints
- 1 <= heights.length <= 100
- 1 <= heights[i] <= 100
Solution Approach
Sort and Compare
Create a copy of the heights array and sort it to generate the expected order. Then iterate through both arrays simultaneously and count indices where the heights differ. This directly solves the mismatch count problem.
Counting Sort Optimization
Because heights are integers in a small range, use counting sort to generate the expected array. This reduces time complexity and avoids the overhead of comparison-based sorting while maintaining accuracy.
Single-Pass Validation
Instead of storing the sorted array, track counts of each height and iterate through heights. Compare counts to current heights in a single pass to increment mismatch count, optimizing space while leveraging the pattern of small-range integers.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(d \cdot (n + b)) |
| Space | O(n + b) |
Time complexity is O(d * (n + b)) using counting sort where n is the array length and b is the maximum height value. Space complexity is O(n + b) for the copy and frequency counts.
What Interviewers Usually Probe
- Expect a solution that leverages sorting for mismatch detection.
- Hint towards using counting sort because heights have a small fixed range.
- Watch for off-by-one errors when comparing indices between original and sorted arrays.
Common Pitfalls or Variants
Common pitfalls
- Assuming heights are unique and failing when duplicates exist.
- Comparing values incorrectly due to array index mismatch.
- Using a slower O(n log n) sort without recognizing counting sort optimization.
Follow-up variants
- Return indices of students out of place instead of count.
- Compute minimal swaps required to sort the heights.
- Handle larger ranges of heights efficiently without counting sort.
How GhostInterview Helps
- Automatically generates the sorted expected array and identifies mismatches quickly.
- Highlights edge cases like duplicates and all-matched arrays to avoid common mistakes.
- Provides optimized counting sort approach to minimize time and space usage for small-range heights.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern behind the Height Checker problem?
The core pattern is comparing an array against its sorted version to count mismatches, often optimized using counting sort.
Can I use a standard sort instead of counting sort?
Yes, a standard sort works, but counting sort is more efficient due to the small range of heights.
How do I handle duplicate heights in the array?
Duplicates are valid; counting sort naturally handles repeated values when generating the expected order.
What should I return if all students are already in order?
Return 0 since there are no mismatched indices between heights and expected sorted order.
Is there a way to reduce space usage when solving Height Checker?
Yes, use frequency counts to compare expected heights without creating a full sorted copy of the array.
Need direct help with Height Checker instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Height Checker from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Sort arr1 by the relative order of arr2, with remaining elements placed in ascending order.
Open problem page#912 Sort an ArraySort an array using an optimal algorithm, focusing on time and space complexity considerations.
Open problem page#1365 How Many Numbers Are Smaller Than the Current NumberIn this problem, you need to determine how many numbers are smaller than each element in an array, focusing on array scanning and hash lookup.
Open problem page