# 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

| Item | Meaning |
|---|---|
| Input | Array `heights` |
| Output | Number of positions where height differs from sorted order |

Function shape:

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

## Examples

Example 1:

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

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

Differences at indices 2, 4, 5.

Answer:

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting |
| Space | `O(n)` | Sorted copy |

## 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

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

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `[1,1,4,2,1,3]` | `3` | Three out-of-order students |
| Reversed | `5` | All except first need to move |
| Already sorted | `0` | No mismatches |