LeetCode 1051 - Height Checker

LeetCode Problem 1051

Difficulty: 🟢 Easy
Topics: Array, Sorting, Counting Sort

Solution

Problem Understanding

The problem gives us an array called heights, where each value represents the height of a student standing in a line. The school wants the students arranged in non-decreasing order, meaning heights should appear from smallest to largest, allowing duplicates.

We are asked to determine how many students are currently standing in the wrong position compared to the correctly sorted order.

In other words, we need to:

1. Create the correctly ordered version of the array.
2. Compare the original array with the sorted version.
3. Count how many indices contain different values.

For example, if:

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

then indices 2, 4, and 5 differ, so the answer is 3.

The constraints are small:

• The array length is at most 100
• Each height is between 1 and 100

These constraints tell us several important things:

• A standard sorting solution is completely acceptable.
• Because the height values are limited to a small fixed range, counting sort is also a very natural optimization.
• Memory usage is not a concern for this problem.

There are several edge cases worth considering:

• The array may already be sorted, producing an answer of 0.
• Every position may be incorrect.
• Multiple students can have the same height, so duplicate handling must work correctly.
• The array may contain only one element.

Approaches

Brute Force Approach

A naive way to solve the problem would be to generate every possible non-decreasing arrangement and compare it against the input array. This would technically allow us to find the expected ordering and count mismatches.

However, generating permutations is extremely inefficient because the number of permutations grows factorially with the size of the array. Even though the constraints are small, factorial growth becomes impractical very quickly.

A slightly better brute-force interpretation is to simply sort a copy of the array using a comparison-based sorting algorithm, then compare the original and sorted arrays index by index.

This works because the sorted array directly represents the expected arrangement of students.

Key Insight

The crucial observation is that we do not need to rearrange the original array in place. We only need to know what the correct sorted order looks like.

Once we have the sorted version:

• If heights[i] == expected[i], that student is already in the correct position.
• Otherwise, that index contributes to the answer.

Since the height values are restricted to 1 through 100, we can use counting sort efficiently.

Counting sort works well here because:

• The value range is very small and fixed.
• Counting frequencies is linear time.
• Reconstructing the sorted order is also linear time.

This gives us an optimal linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force using standard sorting	O(n log n)	O(n)	Sort a copy, then compare indices
Optimal using Counting Sort	O(n + k)	O(k)	Uses bounded height range, where k = 100

Algorithm Walkthrough

Optimal Counting Sort Algorithm

1. Create a frequency array of size 101.

Since heights range from 1 to 100, we can store how many times each height appears. Index i represents height i. 2. Count the frequency of each height.

Traverse the heights array once and increment the corresponding counter. 3. Reconstruct the expected sorted order implicitly.

Instead of creating a fully sorted array immediately, we iterate through possible heights from 1 to 100. 4. Compare against the original array.

Maintain a pointer into the original heights array. For each height value that appears in the frequency array:

• Place that height into the conceptual sorted order.
• Compare it with the current value in heights.
• If they differ, increment the mismatch counter.

5. Continue until all frequencies are exhausted.

At the end, the mismatch counter is the answer.

Why it works

The counting array stores exactly how many times each height must appear in the sorted arrangement. Iterating through the counts in ascending order reconstructs the unique non-decreasing ordering required by the problem. Every comparison checks whether the original position already matches the correct sorted value. Therefore, every mismatch corresponds exactly to a student standing in the wrong position.

Python Solution

from typing import List

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        frequency = [0] * 101

        # Count occurrences of each height
        for height in heights:
            frequency[height] += 1

        mismatch_count = 0
        index = 0

        # Reconstruct sorted order and compare
        for height in range(1, 101):
            while frequency[height] > 0:
                if heights[index] != height:
                    mismatch_count += 1

                index += 1
                frequency[height] -= 1

        return mismatch_count

The implementation begins by creating a frequency array large enough to store counts for every possible height from 1 to 100.

The first loop counts how many times each height appears. This replaces the need for a comparison-based sorting algorithm.

The variable index tracks our current position in the original heights array. We then iterate through heights in ascending order. For every occurrence of a height, we compare the expected sorted value with the original value at the same index.

Whenever the values differ, we increment mismatch_count.

Because we process heights in ascending order, the reconstructed sequence exactly matches the sorted order required by the problem.

Go Solution

func heightChecker(heights []int) int {
	frequency := make([]int, 101)

	// Count occurrences of each height
	for _, height := range heights {
		frequency[height]++
	}

	mismatchCount := 0
	index := 0

	// Reconstruct sorted order and compare
	for height := 1; height <= 100; height++ {
		for frequency[height] > 0 {
			if heights[index] != height {
				mismatchCount++
			}

			index++
			frequency[height]--
		}
	}

	return mismatchCount
}

The Go implementation follows the same logic as the Python version.

The frequency array is created using make([]int, 101). Go slices are zero-initialized automatically, so all frequencies begin at zero.

The nested loop reconstructs the sorted order directly from the counts. Since the maximum height is only 100, integer overflow is not a concern.

Go slices naturally handle empty and non-empty inputs consistently, although this problem guarantees at least one element.

Worked Examples

Example 1

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

Step 1: Build Frequency Array

Height	Count
1	3
2	1
3	1
4	1

Step 2: Reconstruct Sorted Order and Compare

Expected sorted order:

[1,1,1,2,3,4]

Index	Original	Expected	Match?	Mismatches
0	1	1	Yes	0
1	1	1	Yes	0
2	4	1	No	1
3	2	2	Yes	1
4	1	3	No	2
5	3	4	No	3

Final answer:

3

Example 2

Input: heights = [5,1,2,3,4]

Sorted order:

[1,2,3,4,5]

Index	Original	Expected	Match?	Mismatches
0	5	1	No	1
1	1	2	No	2
2	2	3	No	3
3	3	4	No	4
4	4	5	No	5

Final answer:

5

Example 3

Input: heights = [1,2,3,4,5]

Sorted order:

[1,2,3,4,5]

Index	Original	Expected	Match?	Mismatches
0	1	1	Yes	0
1	2	2	Yes	0
2	3	3	Yes	0
3	4	4	Yes	0
4	5	5	Yes	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + k)	Count frequencies and reconstruct sorted order
Space	O(k)	Frequency array of size 101

Here, n is the number of students and k is the range of possible heights.

Since k = 100 is fixed and constant, the algorithm effectively runs in linear time relative to the input size.

The space usage is also constant in practice because the frequency array size never changes.

Test Cases

from typing import List

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        frequency = [0] * 101

        for height in heights:
            frequency[height] += 1

        mismatch_count = 0
        index = 0

        for height in range(1, 101):
            while frequency[height] > 0:
                if heights[index] != height:
                    mismatch_count += 1

                index += 1
                frequency[height] -= 1

        return mismatch_count

solution = Solution()

assert solution.heightChecker([1,1,4,2,1,3]) == 3  # example with duplicates
assert solution.heightChecker([5,1,2,3,4]) == 5  # every position incorrect
assert solution.heightChecker([1,2,3,4,5]) == 0  # already sorted
assert solution.heightChecker([1]) == 0  # single element
assert solution.heightChecker([2,1]) == 2  # smallest unsorted case
assert solution.heightChecker([1,1,1,1]) == 0  # all equal values
assert solution.heightChecker([4,3,2,1]) == 4  # reverse order
assert solution.heightChecker([1,2,2,1,1,2]) == 4  # repeated values
assert solution.heightChecker([100,1,100,1]) == 2  # boundary height values
assert solution.heightChecker([3,3,2,2,1,1]) == 4  # grouped descending duplicates

Test	Why
[1,1,4,2,1,3]	Validates mixed ordering with duplicates
[5,1,2,3,4]	Validates case where every index mismatches
[1,2,3,4,5]	Confirms already sorted input
[1]	Smallest valid input
[2,1]	Small unsorted array
[1,1,1,1]	Ensures duplicates handled correctly
[4,3,2,1]	Reverse sorted order
[1,2,2,1,1,2]	Tests repeated alternating values
[100,1,100,1]	Tests boundary height values
[3,3,2,2,1,1]	Validates descending duplicates

Edge Cases

Already Sorted Input

An already sorted array can expose bugs where the algorithm incorrectly counts mismatches during reconstruction. For example:

[1,2,3,4,5]

Every comparison should match perfectly, resulting in 0. The implementation handles this correctly because mismatches are counted only when values differ.

All Elements Identical

Arrays such as:

[2,2,2,2]

can cause issues in poorly implemented sorting logic, especially if duplicate handling is incorrect. The counting sort approach naturally handles duplicates because frequencies accurately represent repeated values.

Reverse Sorted Order

A descending array such as:

[5,4,3,2,1]

maximizes disorder and tests whether every position is checked independently. The implementation reconstructs the fully sorted order and compares every index, ensuring all mismatches are counted correctly.

Boundary Height Values

The problem allows heights from 1 to 100. Inputs like:

[100,1,100,1]

verify that the frequency array indexing works correctly at both extremes of the valid range. Since the implementation allocates an array of size 101, indices 1 through 100 are safely accessible.