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 <= 1001 <= heights[i] <= 100This approach involves creating an 'expected' array by sorting the given 'heights' array. Once sorted, you compare each element of the original 'heights' array with the corresponding element in the 'expected' array. Count the number of mismatches, which will be your answer.
In C, we first copy the original 'heights' array into an 'expected' array. We then sort the 'expected' array using quicksort, provided by the standard library. We iterate over both arrays, counting indices where 'heights[i]' differs from 'expected[i]'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store the 'expected' array.
Given the constraint that heights range between 1 and 100, we can use a counting sort based approach to find deviations from the expected array without explicitly sorting.
In C, maintain an array 'countHeights' to track frequency of each height from 1 to 100. Use this to simulate creating a sorted version of 'heights' without actually sorting, while counting mismatches directly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + k) where k is 100 (a constant, heights range). Space Complexity: O(k) for the count array.
| Approach | Complexity |
|---|---|
| Sorting and Comparison | Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store the 'expected' array. |
| Counting Sort Optimization | Time Complexity: O(n + k) where k is 100 (a constant, heights range). Space Complexity: O(k) for the count array. |
Balanced Binary Tree - Leetcode 110 - Python • NeetCode • 306,385 views views
Watch 9 more video solutions →Practice Height Checker with our built-in code editor and test cases.
Practice on FleetCode