Height Checker

Problem Description

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the i-th student in line. You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the i-th student in line. Return the number of indices where heights[i] != expected[i].

Key Insights

• The problem requires comparing two arrays: the current heights and the expected sorted heights.
• We can determine the expected heights by sorting the heights array.
• The result is the count of indices where the two arrays differ.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(n) - if we consider the space used by the sorted array.

Solution

To solve the problem, we first create a sorted version of the heights array, which represents the expected order of students by height. Then, we iterate through both the original heights and the sorted array simultaneously, counting how many indices have different values. This approach effectively utilizes sorting and a single pass comparison, ensuring we accurately determine the number of mismatched indices.

Code Solutions