1051. Height Checker
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 72.1%
Problem Breakdown
The problem requires us to determine how many students are not standing in the expected order by height. We are given two arrays: heights, which represents the current order of students, and expected, which represents the non-decreasing order of heights. The task is to count the number of indices where the values in heights do not match the corresponding values in expected.
Inputs:
heights: An integer array representing the current order of student heights.expected: An integer array representing the expected order of student heights.
Outputs:
- An integer count of indices where
heights[i] != expected[i].
Implicit Constraints/Edge Cases:
- The length of both arrays is between 1 and 100.
- Each height value is between 1 and 100.
- The
expectedarray is always sorted in non-decreasing order.
Intuition
A brute-force approach would involve sorting the heights array and comparing it element by element with the expected array. This would work but has a time complexity of O(n log n) due to the sorting step, which is not optimal given that we can achieve better performance.
The key insight is that since the expected array is already sorted in non-decreasing order, we can sort the heights array and compare it directly with expected. This way, we can determine how many students are out of place by counting the number of mismatched indices.
Approach
- Sort the Heights Array: Sort the
heightsarray to get the non-decreasing order. - Compare with Expected: Compare the sorted
heightsarray with theexpectedarray. - Count Mismatches: Count the number of indices where the values in the sorted
heightsarray do not match the corresponding values in theexpectedarray.
Data Structure Choice:
- We use a list to store the sorted version of the
heightsarray.
Complexity Analysis
- Time Complexity: O(n log n) due to the sorting step.
- Space Complexity: O(n) for storing the sorted version of the
heightsarray.
Solution
def heightChecker(heights):
# Sort the heights array to get the expected order
sorted_heights = sorted(heights)
# Count the number of indices where heights[i] != expected[i]
mismatch_count = sum(1 for i in range(len(heights)) if heights[i] != sorted_heights[i])
return mismatch_count
# Example usage:
print(heightChecker([1, 1, 4, 2, 1, 3])) # Output: 3
print(heightChecker([5, 1, 2, 3, 4])) # Output: 5
print(heightChecker([1, 2, 3, 4, 5])) # Output: 0
Edge Cases Handled
- All elements are in the correct order: The function returns 0 as there are no mismatches.
- All elements are in the wrong order: The function returns the length of the array as all indices mismatch.
- Single element array: The function correctly handles arrays with a single element, returning 0 if it’s already sorted or 1 if not.
The solution provided is correct and efficient given the constraints. It accurately addresses the problem statement and handles all edge cases as described.