💬 Discord
Sign In
NeetCode #60LC-1051EasyArrays & Hashing
← Back to All Problems

#60 · #1051 · Height Checker(高度检查器)

📌 Problem Statement & Constraints

Students are asked to stand in non-decreasing order of height. Given the current order in heights, return the number of indices where the current order does not match the sorted order. Constraints: 1 <= heights.length <= 100, 1 <= heights[i] <= 100.

💡 Core Algorithmic Approaches

  1. The expected order is simply the sorted array, so build it and compare position by position.
  2. Count the indices where the two differ.
  3. Because the value range is only 1..100, counting sort is a viable O(n + V) alternative to a comparison sort.
  4. The answer is the minimum number of moves needed, since each mismatched position needs exactly one student relocated.

💻 Benchmark Python3 Implementation

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        return sum(1 for a, b in zip(heights, expected) if a != b)


# Counting sort: exploits the bounded value range 1..100
class Solution2:
    def heightChecker(self, heights: List[int]) -> int:
        cnt = [0] * 101
        for h in heights:
            cnt[h] += 1
        i = 0
        res = 0
        for h in range(1, 101):
            for _ in range(cnt[h]):
                if heights[i] != h:        # compare against the sorted stream
                    res += 1
                i += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n) for the sort-based version, O(n + V) for the counting-sort version with V = 100.
💾 Space Complexity
O(n) for the sorted copy; O(V) = O(1) for the counting version.

⚠️ Interview Pitfalls & Follow-ups

  • Counting inversions instead of position mismatches: the answer is the number of positions where the arrays differ, not the number of out-of-order pairs.
  • Sorting the input in place and then comparing: after sorting, the original order is lost, so a copy is needed.
  • Assuming heights contains distinct values: duplicates are allowed, and equal values must be matched positionally.