Height Checker: Sort and Compare Pattern

LeetCode Height Checker (problem 1051) asks you to count how many students are not standing in the right position. You are given an array heights representing the current order of students, and you need to figure out how many of them would need to move if the line were sorted in non-decreasing order.

The problem

Given heights = [1, 1, 4, 2, 1, 3], the expected non-decreasing order is [1, 1, 1, 2, 3, 4]. Compare each index: positions 0 and 1 match, but positions 2, 4, and 5 do not. The answer is 3.

The problem is really asking: how many positions differ between the original array and its sorted version? That framing makes the solution clear.

The approach

The strategy is simple: sort a copy of the array, then walk through both arrays and count the positions where the values differ.

1. Create a sorted copy of heights (call it expected)
2. Loop through every index
3. If heights[i] does not equal expected[i], increment a counter
4. Return the counter

That is it. No fancy data structures, no tricky edge cases. Just sort and compare.

The code

def height_checker(heights: list[int]) -> int:
    expected = sorted(heights)
    return sum(1 for i in range(len(heights)) if heights[i] != expected[i])

Line by line:

• expected = sorted(heights) creates a new list that is the sorted version of the input. The original heights array stays unchanged.
• sum(1 for i in range(len(heights)) if heights[i] != expected[i]) walks through each index, checks if the value in the original array differs from the sorted version, and counts how many times that happens.

You could also write the counting part as a loop:

def height_checker(heights: list[int]) -> int:
    expected = sorted(heights)
    count = 0
    for i in range(len(heights)):
        if heights[i] != expected[i]:
            count += 1
    return count

Both versions do the same thing. The generator expression is just more concise.

Visual walkthrough

Let's trace through heights = [1, 1, 4, 2, 1, 3] step by step. At each position, we compare the original value against the expected sorted value and decide if it is a mismatch.

Notice the pattern: each comparison is independent. You do not need any information from previous comparisons to evaluate the current one. This makes the counting pass trivially parallelizable and easy to reason about.

Complexity analysis

The sort-and-compare approach takes O(n log n) time because sorting dominates. The comparison pass is O(n). Space is O(n) for the sorted copy.

Since the constraints say heights are between 1 and 100, you can use counting sort to bring the time down to O(n). Build a frequency array, then reconstruct the sorted order from it:

def height_checker(heights: list[int]) -> int:
    counts = [0] * 101
    for h in heights:
        counts[h] += 1

    count = 0
    expected_idx = 0
    for h in heights:
        while counts[expected_idx] == 0:
            expected_idx += 1
        if h != expected_idx:
            count += 1
        counts[expected_idx] -= 1

    return count

For interview purposes, the O(n log n) sorting approach is perfectly fine and easier to write correctly. Mention the counting sort optimization if asked about follow-ups.

Building blocks

Sort and compare

The core pattern here is "sort a copy, then compare with the original." You sort to establish the target ordering, and then you measure how much the original deviates from that target. This same idea appears in many problems:

• Relative Ranks (LeetCode 506): sort to determine rank order, then map ranks back to original positions
• Minimum Swaps to Sort (various): sort, then count how many elements are out of place
• Wiggle Sort problems: sort first, then rearrange according to a pattern

Whenever a problem asks "how different is this array from its sorted form?", this is the pattern to reach for.

Counting sort

When the value range is small and known (like 1 to 100 in this problem), counting sort lets you sort in O(n) time. Instead of comparison-based sorting, you count occurrences of each value and reconstruct the sorted array from those counts. This is a useful optimization to mention in interviews, especially when the constraints make it obvious.

Edge cases

• Already sorted: every position matches, so the answer is 0
• Reverse sorted: every position is a mismatch (maximum possible answer)
• All identical values: sorted is the same as the original, so the answer is 0
• Single element: always returns 0 since a single-element array is already sorted
• Two elements: either 0 (if in order) or 2 (if swapped)

From understanding to recall

This is an easy problem, and you might think that means you can skip drilling it. But "easy to understand" and "instantly recallable under pressure" are different things. In an interview, you want the sort-and-compare pattern to be automatic. When you see "how many elements are out of place?", you should immediately think "sort a copy and count differences."

Spaced repetition builds that kind of automatic recognition. You solve this problem today, then revisit it in a few days, then a week later. Each pass makes the pattern more reflexive. The goal is not to memorize this specific solution. The goal is to internalize the sort-and-compare pattern so deeply that it becomes your default tool for any "measure deviation from sorted order" problem.

Related posts

• Sort Colors - A partitioning problem where you sort elements into categories in a single pass.
• Sort an Array - Build merge sort from scratch to understand the sorting step that powers this pattern.
• Relative Ranks - Another problem where sorting determines the answer, but you map results back to original positions.

Height Checker is one of those problems that rewards clear thinking over clever tricks. The entire solution is "sort and compare." That simplicity is the point. Recognizing when a problem reduces to sorting is a skill that pays off across dozens of other problems. Build that recognition through practice, and the next time you see a problem that asks "how far is this from sorted?", you will know exactly where to start.