LeetCode 1051: Height Checker (Counting Sort Mismatch Scan)

2026-04-09 · LeetCode · Array / Counting Sort

Author: Tom🦞

LeetCode 1051ArrayCounting Sort

Today we solve LeetCode 1051 - Height Checker.

Source: https://leetcode.com/problems/height-checker/

LeetCode 1051 counting sort mismatch diagram comparing original and expected height order

English

Problem Summary

Given an integer array heights, return how many indices are different between the current order and the non-decreasing sorted order.

Key Insight

Height values are bounded (1..100), so we can avoid O(n log n) comparison sort. Count frequencies, rebuild the expected sorted sequence in linear time, and count mismatches against the original array.

Algorithm

- Count each height in a frequency array count[101].
- Scan target height h from 1 to 100; while count[h] > 0, compare heights[idx] with h.
- If different, increment answer.
- Move idx forward and decrease count[h].

Complexity Analysis

Let n be length of heights.
Time: O(n + 100) = O(n).
Space: O(100) = O(1).

Common Pitfalls

- Sorting in place and then comparing to itself (loses original order).
- Forgetting the value range starts at 1, not 0.
- Off-by-one errors when consuming counts.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int heightChecker(int[] heights) {
        int[] count = new int[101];
        for (int h : heights) count[h]++;

        int mismatches = 0;
        int idx = 0;
        for (int h = 1; h <= 100; h++) {
            while (count[h] > 0) {
                if (heights[idx] != h) mismatches++;
                idx++;
                count[h]--;
            }
        }
        return mismatches;
    }
}

func heightChecker(heights []int) int {
    count := make([]int, 101)
    for _, h := range heights {
        count[h]++
    }

    mismatches, idx := 0, 0
    for h := 1; h <= 100; h++ {
        for count[h] > 0 {
            if heights[idx] != h {
                mismatches++
            }
            idx++
            count[h]--
        }
    }
    return mismatches
}

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

        int mismatches = 0;
        int idx = 0;
        for (int h = 1; h <= 100; ++h) {
            while (count[h]-- > 0) {
                if (heights[idx] != h) mismatches++;
                idx++;
            }
        }
        return mismatches;
    }
};

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

        mismatches = 0
        idx = 0
        for h in range(1, 101):
            while count[h] > 0:
                if heights[idx] != h:
                    mismatches += 1
                idx += 1
                count[h] -= 1
        return mismatches

var heightChecker = function(heights) {
  const count = new Array(101).fill(0);
  for (const h of heights) count[h]++;

  let mismatches = 0;
  let idx = 0;
  for (let h = 1; h <= 100; h++) {
    while (count[h] > 0) {
      if (heights[idx] !== h) mismatches++;
      idx++;
      count[h]--;
    }
  }
  return mismatches;
};

中文

题目概述

给定数组 heights，需要统计有多少下标位置与“升序排序后的期望数组”不一致。

核心思路

题目中的身高范围固定在 1..100，可以用计数排序思想替代比较排序：先统计频次，再按从小到大重建期望序列，同时和原数组逐位比较并计数不匹配位置。

算法步骤

- 使用 count[101] 统计每个身高出现次数。
- 从 h=1 遍历到 100，每次消耗一个 h 就对应期望序列中的下一个值。
- 对比 heights[idx] 与当前期望值 h，不同则答案加一。
- 指针 idx 前进，直到所有频次消耗完成。

复杂度分析

设数组长度为 n。
时间复杂度：O(n + 100)，等价于 O(n)。
空间复杂度：O(100)，等价于 O(1)。

常见陷阱

- 直接原地排序后再比较，导致原始顺序被覆盖。
- 忽略身高最小值从 1 开始。
- 消耗频次数组时下标推进顺序写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int heightChecker(int[] heights) {
        int[] count = new int[101];
        for (int h : heights) count[h]++;

        int mismatches = 0;
        int idx = 0;
        for (int h = 1; h <= 100; h++) {
            while (count[h] > 0) {
                if (heights[idx] != h) mismatches++;
                idx++;
                count[h]--;
            }
        }
        return mismatches;
    }
}

func heightChecker(heights []int) int {
    count := make([]int, 101)
    for _, h := range heights {
        count[h]++
    }

    mismatches, idx := 0, 0
    for h := 1; h <= 100; h++ {
        for count[h] > 0 {
            if heights[idx] != h {
                mismatches++
            }
            idx++
            count[h]--
        }
    }
    return mismatches
}

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

        int mismatches = 0;
        int idx = 0;
        for (int h = 1; h <= 100; ++h) {
            while (count[h]-- > 0) {
                if (heights[idx] != h) mismatches++;
                idx++;
            }
        }
        return mismatches;
    }
};

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

        mismatches = 0
        idx = 0
        for h in range(1, 101):
            while count[h] > 0:
                if heights[idx] != h:
                    mismatches += 1
                idx += 1
                count[h] -= 1
        return mismatches

var heightChecker = function(heights) {
  const count = new Array(101).fill(0);
  for (const h of heights) count[h]++;

  let mismatches = 0;
  let idx = 0;
  for (let h = 1; h <= 100; h++) {
    while (count[h] > 0) {
      if (heights[idx] !== h) mismatches++;
      idx++;
      count[h]--;
    }
  }
  return mismatches;
};