Height Checker

How it works

Since heights are constrained to a small range (1 to 100), we can use counting sort for a more efficient solution. Instead of sorting the entire array, we count how many times each height appears. Then we reconstruct the expected sorted order by iterating through possible heights and adding each one according to its count. Finally, we compare the original array with this expected array.

Steps

1. Create a count array of size 101 (to cover heights 1 through 100).
2. Count occurrences of each height in the original array.
3. Build the expected array by iterating from height 1 to 100 and appending each height according to its count.
4. Compare the original array with the expected array and count positions where they differ.
5. Return the mismatch count.

Complexity

• Time complexity: O(n + k)
• Space complexity: O(n + k)

Where n is the size of the input array, and k is the range of numbers.

Things to watch for

Modifying the Original Array

When sorting the array to get the expected order, some developers accidentally sort the original array in place. This destroys the original order, making it impossible to compare positions. Always create a copy of the array before sorting, or use a method that returns a new sorted array without modifying the original.

Using Lexicographic Sort Instead of Numeric Sort

In languages like JavaScript, the default sort() method sorts elements as strings, not numbers. This means [1, 10, 2] would be sorted as [1, 10, 2] instead of [1, 2, 10]. Always provide a numeric comparator function (e.g., (a, b) => a - b) to ensure correct sorting behavior.

from typing import List

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        count = [0] * 101
        for h in heights:
            count[h] += 1

        expected = []
        for h in range(1, 101):
            c = count[h]
            for _ in range(c):
                expected.append(h)

        res = 0
        for i in range(len(heights)):
            if heights[i] != expected[i]:
                res += 1

        return res

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int count[101] = {};
        for (int h : heights) {
            count[h]++;
        }

        vector<int> expected;
        for (int h = 1; h <= 100; h++) {
            int c = count[h];
            for (int i = 0; i < c; i++) {
                expected.push_back(h);
            }
        }

        int res = 0;
        for (int i = 0; i < heights.size(); i++) {
            if (heights[i] != expected[i]) {
                res++;
            }
        }

        return res;
    }
};