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.
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; }}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.