LeetCode 1051: Height Checker

Problem Restatement

We are given an array heights representing the current order of students.

The expected order is the students sorted by height in non-decreasing order.

Return the number of indices where the current height does not match the expected height.

The official constraints state that 1 <= heights.length <= 100 and 1 <= heights[i] <= 100.

Input and Output

Function shape:

def heightChecker(heights: list[int]) -> int:
    ...

Examples

Example 1:

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

Expected: [1, 1, 1, 2, 3, 4].

Differences at indices 2, 4, 5.

Answer:

3

Algorithm

Sort heights and count positions where the original differs.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

Testing

def run_tests():
    s = Solution()

    assert s.heightChecker([1,1,4,2,1,3]) == 3
    assert s.heightChecker([5,1,2,3,4]) == 5
    assert s.heightChecker([1,2,3,4,5]) == 0

    print("all tests passed")

run_tests()