Height Checker
EasyPrompt
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] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This straightforward approach involves first determining the expected order of students. This is achieved by creating a copy of the heights array and sorting it in non-decreasing order. Once we have both the original heights array and the sorted expected array, we can iterate through them simultaneously and count the number of positions where the heights do not match.
Algorithm
- Create a copy of the
heightsarray, let's call itexpected. - Sort the
expectedarray using a standard comparison-based sorting algorithm (e.g.,Arrays.sort()in Java). - Initialize a counter variable,
mismatchCount, to zero. - Iterate from
i = 0toheights.length - 1. - In each iteration, compare
heights[i]withexpected[i]. - If
heights[i] != expected[i], incrementmismatchCount. - After the loop completes, return
mismatchCount.
Walkthrough
The core idea is to generate the target sorted array and then perform a direct comparison.
- Create a Copy: We first create an exact copy of the
heightsarray. We cannot sort the original array in-place because we need it for the final comparison. - Sort: We use a standard library function, like
Arrays.sort(), to sort the copied array. This function typically implements an efficient comparison sort algorithm like Quicksort or Timsort, resulting in an O(N log N) time complexity. - Compare and Count: We then loop through both the original
heightsarray and the newly sortedexpectedarray from the first to the last element. A counter is used to keep track of the number of indicesiwhereheights[i]is not equal toexpected[i]. This count is the final answer.
import java.util.Arrays; class Solution { public int heightChecker(int[] heights) { int n = heights.length; int[] expected = new int[n]; // Create a copy of the heights array. System.arraycopy(heights, 0, expected, 0, n); // Sort the copied array to get the expected order. Arrays.sort(expected); int mismatchCount = 0; // Compare the original array with the sorted array. for (int i = 0; i < n; i++) { if (heights[i] != expected[i]) { mismatchCount++; } } return mismatchCount; }}Complexity
Time
O(N log N), where N is the number of students. The dominant operation is sorting the array. Copying the array and the final comparison loop both take O(N) time, which is overshadowed by the sort.
Space
O(N), where N is the number of students. This space is required to store the copy of the `heights` array.
Trade-offs
Pros
Easy to understand and implement.
The code is concise and relies on well-tested built-in functions.
Cons
Sub-optimal time complexity compared to other methods that can leverage the problem's constraints.
Requires extra space proportional to the input size (O(N)) to store the copied array.
This approach leverages the specific constraints of the problem, namely that the heights are integers within a small, fixed range (1 to 100). Instead of a general-purpose comparison sort, we can use a counting sort-based method. We count the occurrences of each height and then reconstruct the sorted sequence to compare against the original array, leading to a more efficient solution.
Algorithm
- Create a frequency array,
heightFreq, of size 101 (since heights are between 1 and 100) and initialize all its values to 0. - Iterate through the input
heightsarray. For each heighth, increment the count atheightFreq[h]. - Initialize a
mismatchCountto 0 and a pointercurrentHeightto 1. - Iterate through the original
heightsarray using an indexifrom 0 ton-1. - Inside the loop, find the next valid expected height by advancing
currentHeightas long asheightFreq[currentHeight]is 0. - Compare the actual height
heights[i]with the expectedcurrentHeight. If they are different, incrementmismatchCount. - Decrement
heightFreq[currentHeight]to signify that one student of this height has been placed in the expected line. - Return
mismatchCountafter the loop.
Walkthrough
Because the range of heights is small and known, we can avoid an O(N log N) sort.
- Frequency Count: We create an auxiliary array,
heightFreq, of size 101. We iterate through the inputheightsarray once, and for each height, we increment its corresponding index inheightFreq. For example, if we see a height of 5, we doheightFreq[5]++. After this step,heightFreq[h]will store the number of students with heighth. - Simultaneous Traversal and Comparison: We can determine the number of mismatches in a single pass. We iterate through the original
heightsarray from left to right (indexi). For each position, we determine what the expected height should be. We can find this by keeping a pointer,currentHeight, to the smallest height that is supposed to be in the line. We find the first non-zero entry in ourheightFreqarray; this is ourcurrentHeight. We compareheights[i]with thiscurrentHeight. If they don't match, we increment a counter. Then, we decrement the count forcurrentHeightin our frequency map and move to the next positioni+1in theheightsarray. This way, we effectively compare the original array with the sorted version without explicitly creating the sorted array.
class Solution { public int heightChecker(int[] heights) { // Heights are between 1 and 100. int[] heightFreq = new int[101]; // Populate the frequency array. for (int height : heights) { heightFreq[height]++; } int mismatchCount = 0; int currentHeight = 1; // Iterate through the original heights array to compare with the expected order. for (int i = 0; i < heights.length; i++) { // Find the next height that should be in the sorted line. while (heightFreq[currentHeight] == 0) { currentHeight++; } // If the student at the current position doesn't have the expected height, it's a mismatch. if (heights[i] != currentHeight) { mismatchCount++; } // Decrement the frequency for the current expected height, as we've accounted for one student. heightFreq[currentHeight]--; } return mismatchCount; }}Complexity
Time
O(N + K), where N is the number of students and K is the range of heights. The first loop to populate the frequency array is O(N). The second loop also runs N times, and the inner `while` loop's pointer `currentHeight` traverses the range of K just once in total across all iterations. Thus, the total time is O(N + K). Since K is a constant (100), this simplifies to O(N).
Space
O(K), where K is the range of possible heights (101 in this case). Since K is a constant, the space complexity is O(1).
Trade-offs
Pros
Optimal time complexity of O(N) for this problem.
Constant space complexity, as the frequency array's size is fixed and does not depend on the input size N.
Cons
The logic is slightly more complex than the comparison sort approach.
This method's efficiency is highly dependent on the constraint that the range of values is small. It would be inefficient for a large range of heights.
Solutions
Solution
class Solution {public int heightChecker(int[] heights) { int[] expected = heights.clone(); Arrays.sort(expected); int ans = 0; for (int i = 0; i < heights.length; ++i) { if (heights[i] != expected[i]) { ++ans; } } return ans; }}class Solution: def heightChecker(self, heights: List[int]) -> int: expected = sorted(heights) return sum(a != b for a, b in zip(heights, expected))class Solution {public: int heightChecker(vector<int> &heights) { vector<int> expected = heights; sort(expected.begin(), expected.end()); int ans = 0; for (int i = 0; i < heights.size(); ++i) ans += heights[i] != expected[i]; return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.