1051. Height Checker - Explanation

1. Sorting

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)

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

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Counting Sort

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

Time & Space 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.