Height Checker

Height Checker

What is this problem about?

The Height Checker interview question asks you to compare a given array of heights with the "expected" order. The expected order is simply the heights sorted in non-decreasing order. You need to return the number of indices where the actual height in the input array does not match the expected height in the sorted array.

Why is this asked in interviews?

This "Easy" question is used by Amazon and Meta to test basic array manipulation and sorting concepts. It evaluates whether a candidate understands the simplest way to identify differences between two datasets. While the straightforward solution is sorting, it can also lead to discussions about Counting Sort interview patterns, which can solve the problem in linear time when the range of values is small.

Algorithmic pattern used

The standard pattern is Sorting and Comparison.

1. Create a copy of the original heights array.
2. Sort the copied array to create the "expected" order ($O(N \log N)$).
3. Iterate through both arrays simultaneously.
4. Compare elements at each index; if they differ, increment a counter.

Alternatively, since heights are typically within a small range (e.g., 1 to 100), you can use Counting Sort to achieve $O(N)$ time complexity.

Example explanation

Heights: [1, 1, 4, 2, 1, 3]

1. Sorted (Expected): [1, 1, 1, 2, 3, 4]
2. Compare:
   • Index 2: 4 vs 1 (Mismatch)
   • Index 4: 1 vs 3 (Mismatch)
   • Index 5: 3 vs 4 (Mismatch) Result: 3.

Common mistakes candidates make

• In-place Sorting: Sorting the original array without making a copy first, which makes it impossible to perform the comparison.
• Off-by-one: Errors in the loop range when comparing the two arrays.
• Over-engineering: Trying to use complex data structures like Heaps when a simple sort is more efficient and readable.

Interview preparation tip

Always consider the constraints. If the values in an array are constrained to a small range (like 1-100), Counting Sort is a great optimization to mention. It shows you can adapt your approach based on specific data properties to improve time complexity from $O(N \log N)$ to $O(N)$.