{x}
blog image

Height Checker

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 ith 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 ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

 

Example 1:

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
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
Explanation:
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
Explanation:
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 Explanation for Height Checker

The problem asks to find the number of indices where the elements of the input array heights differ from the elements of the sorted array heights (which we'll call expected). This signifies the number of students whose height is not in the correct non-decreasing order.

Two approaches are presented: sorting and counting sort.

Approach 1: Sorting

This is a straightforward approach. We create a copy of the heights array, sort the copy (expected), and then compare the original heights array with the sorted expected array element by element. The number of mismatches is the answer.

Time Complexity: O(n log n) - dominated by the sorting operation. Space Complexity: O(n) - to store the sorted array expected.

Code Examples:

The code examples are provided in multiple languages and use the built-in sorting functionality. The core logic remains the same across all languages: copy the input array, sort the copy, and count mismatches.

Approach 2: Counting Sort

This approach is more efficient if the range of heights is relatively small, as it is in this problem (heights are between 1 and 100). Counting sort has a linear time complexity for this specific constraint.

We use a count array (cnt) to store the frequency of each height. Then, we iterate through the heights array again. For each height, we decrement its count in cnt and compare it with the expected height at the current index. If they mismatch, we increment the mismatch counter (ans).

Time Complexity: O(n + M), where n is the number of students and M is the maximum height (100 in this case). This is essentially linear time because M is a constant. Space Complexity: O(M) - for the counting array cnt.

Code Examples:

The code for counting sort also demonstrates the same fundamental logic across different languages. The difference lies mainly in the syntax and data structure handling. The key is to use the cnt array to efficiently track the frequency of each height, allowing for a linear time comparison.

In summary:

The sorting approach is simpler to understand and implement, but less efficient for this specific problem with a limited height range. The counting sort approach offers better performance in this scenario due to its linear time complexity. Choose the approach based on your priorities (simplicity vs. efficiency) and the constraints of your specific application.