Domain 1EasyCORE

Height Checker

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`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

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 expected array 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

  1. Sort the Heights Array: Sort the heights array to get the non-decreasing order.
  2. Compare with Expected: Compare the sorted heights array with the expected array.
  3. Count Mismatches: Count the number of indices where the values in the sorted heights array do not match the corresponding values in the expected array.

Data Structure Choice:

  • We use a list to store the sorted version of the heights array.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step.
  • Space Complexity: O(n) for storing the sorted version of the heights array.

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.