#1051

Easy

LeetCode Problem Workspace

Height Checker

Determine how many students are out of place in a line by comparing their heights to the sorted expected order efficiently.

array sorting counting sort

Problem Statement

A school wants to photograph students standing in a single file line in non-decreasing height order. You are given an integer array heights representing the current order of students, where heights[i] is the height of the ith student.

Return the number of indices where the current arrangement does not match the expected sorted order. For example, if a student is taller or shorter than the expected height at the same position, it counts as a mismatch.

Examples

Example 1

Input: heights = [1,1,4,2,1,3]

Output: 3

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

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

heights: [1,2,3,4,5] expected: [1,2,3,4,5] All indices match.

Constraints

1 <= heights.length <= 100
1 <= heights[i] <= 100

Solution Approach

Sort and Compare

Create a copy of the heights array and sort it to generate the expected order. Then iterate through both arrays simultaneously and count indices where the heights differ. This directly solves the mismatch count problem.

Counting Sort Optimization

Because heights are integers in a small range, use counting sort to generate the expected array. This reduces time complexity and avoids the overhead of comparison-based sorting while maintaining accuracy.

Single-Pass Validation

Instead of storing the sorted array, track counts of each height and iterate through heights. Compare counts to current heights in a single pass to increment mismatch count, optimizing space while leveraging the pattern of small-range integers.

Complexity Analysis

Metric	Value
Time	O(d \cdot (n + b))
Space	O(n + b)

Time complexity is O(d * (n + b)) using counting sort where n is the array length and b is the maximum height value. Space complexity is O(n + b) for the copy and frequency counts.

What Interviewers Usually Probe

Expect a solution that leverages sorting for mismatch detection.
Hint towards using counting sort because heights have a small fixed range.
Watch for off-by-one errors when comparing indices between original and sorted arrays.

Common Pitfalls or Variants

Common pitfalls

Assuming heights are unique and failing when duplicates exist.
Comparing values incorrectly due to array index mismatch.
Using a slower O(n log n) sort without recognizing counting sort optimization.

Follow-up variants

Return indices of students out of place instead of count.
Compute minimal swaps required to sort the heights.
Handle larger ranges of heights efficiently without counting sort.

FAQ

What is the main pattern behind the Height Checker problem?

The core pattern is comparing an array against its sorted version to count mismatches, often optimized using counting sort.

Can I use a standard sort instead of counting sort?

Yes, a standard sort works, but counting sort is more efficient due to the small range of heights.

How do I handle duplicate heights in the array?

Duplicates are valid; counting sort naturally handles repeated values when generating the expected order.

What should I return if all students are already in order?

Return 0 since there are no mismatched indices between heights and expected sorted order.

Is there a way to reduce space usage when solving Height Checker?

Yes, use frequency counts to compare expected heights without creating a full sorted copy of the array.

terminal

Solution

Solution 1: Sorting

We can first sort the heights of the students, then compare the sorted heights with the original heights, and count the positions that are different.

1

2

3

4

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        return sum(a != b for a, b in zip(heights, expected))

Solution 2: Counting Sort

Since the height of the students in the problem does not exceed $100$, we can use counting sort. Here we use an array $cnt$ of length $101$ to count the number of times each height $h_i$ appears.

1

2

3

4

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        return sum(a != b for a, b in zip(heights, expected))

Continue Practicing

#1122 relative sort array #912 sort an array #1365 how many numbers are smaller than the current number