Height Checker - Solution & Explanation

Problem Overview: You receive an array heights representing student heights in the order they currently stand. Students should be arranged in non‑decreasing order. The task is to count how many indices contain a height different from the height that would appear in the correctly sorted order.

Approach 1: Sorting and Comparison (O(n log n) time, O(n) space)

The most direct solution is to compute what the correct ordering should look like. Create a copy of the heights array and sort it using a standard sorting algorithm. Then iterate through both arrays simultaneously and count how many indices differ. Each mismatch represents a student who is not in the position they would occupy in the sorted lineup. This approach is simple, easy to implement in any language, and works well because the problem only requires comparison against the sorted order rather than modifying the original array.

The key insight is that the sorted array represents the expected arrangement. By comparing index by index, you avoid complex rearrangement logic. The algorithm performs one sort operation and one linear pass through the array, leading to O(n log n) time complexity and O(n) additional space for the copy.

Approach 2: Counting Sort Optimization (O(n + k) time, O(k) space)

The constraints of the problem reveal that student heights fall within a small fixed range (1 to 100). Instead of sorting explicitly, you can use counting sort. Create a frequency array where index i stores how many students have height i. This structure lets you reconstruct the sorted order implicitly without performing comparisons.

Traverse the original heights array while maintaining a pointer that represents the current expected height in sorted order. Move this pointer forward through the frequency array until you find a height with remaining count. If the expected height differs from the current element in the original array, increment the mismatch counter. Decrease the frequency and continue. Because each element is processed once and the height range k is constant (100), the runtime becomes O(n + k), which effectively behaves like O(n).

This approach uses ideas from array frequency counting and works best when the value range is limited. It avoids the O(n log n) cost of general sorting and is considered the optimal solution for this problem.

Recommended for interviews: Start with the sorting comparison solution because it clearly demonstrates understanding of the problem. After that, mention the counting sort optimization once you recognize the bounded height range. Interviewers often expect candidates to notice this constraint and reduce the complexity from O(n log n) to near O(n).