File: height-checker/solution.py

Date: 2026-06-06

Time: 17:00

Height Checker — height-checker/solution.py

Purpose

Solves LeetCode 1051 — Height Checker: given an array of student heights, count how many students are standing in the wrong position relative to the non-decreasing sorted order. This file owns the single solution function and is imported by height-checker/test_solution.py.

Key Components

height_checker(heights: list[int]) -> int — The sole public function. Takes a list of heights (values 1–100) and returns the number of indices where the current order disagrees with the sorted order.

Patterns

Counting sort. Instead of calling sorted() (O(n log n)), the solution exploits the constrained value range (1–100) to sort in O(n + k) where k=100. It builds a frequency array counts of size 101 (index 0 unused), then walks through it to reconstruct the sorted order on the fly — without ever materializing the sorted array.

Single-pass comparison against virtual sorted order. The variable j acts as a cursor into the conceptual sorted array. For each element in heights, the code advances j past any exhausted values (counts[j] == 0), compares h to j (the next expected sorted value), and decrements the count. This fuses the "generate sorted array" and "compare" steps into one loop.

Dependencies

• Imports: None — pure stdlib, no external dependencies.
• Imported by: height-checker/testsolution.py directly. The "Imported By" list in the prompt is misleading — those are unrelated test files that happen to share a common test harness pattern, not actual consumers of heightchecker.

Flow

1. Build frequency table — iterate heights, incrementing counts[h] for each value. O(n).

2. Walk sorted order — iterate heights a second time. For each h:

• Advance j until counts[j] > 0 (skip values with zero remaining count).
• If h != j, the student is out of position — increment mismatches.
• Decrement counts[j] to "consume" one instance of that sorted value.

3. Return mismatches.

Invariants

• Value range [1, 100]: The 101-element array assumes heights are in this range. Values outside it would index out of bounds or be silently ignored at index 0.
• j only advances forward: Because the sorted order is non-decreasing, j never needs to backtrack. Each value in counts is consumed exactly once across the full loop, so the total inner while iterations across all outer iterations is O(k).
• Total counts consumed equals n: Every element contributes +1 during the build phase and exactly -1 during the comparison phase, so the frequency table reaches all zeros by the end.

Error Handling

None. The function trusts its input matches the LeetCode contract (non-empty list, values 1–100). Out-of-range values would cause an IndexError (values > 100) or silently pollute index 0 (value 0). Empty input would return 0 correctly since the loop body wouldn't execute.