What is the time complexity of the Sorting approach?

The Sorting approach has a time complexity of O(n log n) due to the sorting operation.

What is the time complexity of the Counting Sort approach?

The Counting Sort approach has a time complexity of O(n) since we only iterate through the array once and then through the fixed range of 1-100.

Why is Counting Sort optimal for this problem?

Counting Sort is optimal because the problem constraints limit heights to values between 1 and 100, allowing us to use a fixed-size count array and achieve linear time complexity.

What is the space complexity of the Counting Sort approach?

The space complexity is O(1) because the count array has a fixed size of 101 regardless of the input size.

Height Checker | N3mo LC

Difficulty: Easy | Acceptance: 81.70% | Paid: No Topics: Array, Sorting, Counting Sort

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Examples
Constraints
Sorting Approach
Counting Sort Approach

Examples

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
heights:  [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.

Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights:  [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.

Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights:  [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.

Constraints

1 <= heights.length <= 100
1 <= heights[i] <= 100

Sorting Approach

Intuition Create a sorted copy of the heights array and compare it with the original array element by element to count mismatches.

Steps

Create a copy of the heights array and sort it in non-decreasing order
Iterate through both arrays simultaneously
Count positions where elements differ
Return the count

python

class Solution:
    def heightChecker(self, heights: List[int]) -&gt; int:
        expected = sorted(heights)
        count = 0
        for i in range(len(heights)):
            if heights[i] != expected[i]:
                count += 1
        return count

Complexity

Time: O(n log n) for sorting
Space: O(n) for the sorted copy
Notes: Simple and intuitive, but not optimal given the constraint that heights are limited to 1-100

Counting Sort Approach

Intuition Since heights are constrained between 1 and 100, we can use counting sort to achieve O(n) time complexity by counting frequency of each height.

Steps

Create a count array of size 101 initialized to 0
Count the frequency of each height in the input array
Iterate through heights 1 to 100, and for each height, compare with original array positions
Count mismatches and decrement frequency as we consume each height
Return the total mismatch count

python

class Solution:
    def heightChecker(self, heights: List[int]) -&gt; int:
        count = [0] * 101
        for h in heights:
            count[h] += 1
        
        result = 0
        i = 0
        for h in range(1, 101):
            while count[h] &gt; 0:
                if heights[i] != h:
                    result += 1
                count[h] -= 1
                i += 1
        return result

Complexity

Time: O(n) where n is the length of heights array
Space: O(1) since count array is fixed size 101
Notes: Optimal solution leveraging the constraint that heights are between 1 and 100