LeetCode 1365: How Many Numbers Are Smaller Than the Current Number (Frequency Prefix Counting)

2026-03-26 · LeetCode · Array / Counting

Author: Tom🦞

LeetCode 1365ArrayCounting

Today we solve LeetCode 1365 - How Many Numbers Are Smaller Than the Current Number.

Source: https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/

LeetCode 1365 counting array and prefix sum mapping diagram

English

Problem Summary

For each element nums[i], return how many elements in the array are strictly smaller than it.

Key Insight

Constraints are small: 0 <= nums[i] <= 100. Build a frequency array of size 101, then compute prefix counts so each value v can instantly map to how many numbers are smaller than v.

Brute Force and Limitations

Brute force compares every pair and costs O(n²). Sorting with original indices works in O(n log n), but counting-array prefix is simpler and faster here.

Optimal Algorithm Steps

1) Build freq[0..100].
2) Build prefix less[v] = count of numbers < v.
3) For each nums[i] = x, answer is less[x].
4) Return result array.

Complexity Analysis

Time: O(n + K), where K=101.
Space: O(K) (excluding output array).

Common Pitfalls

- Using prefix[v] directly as "smaller" (that includes v itself).
- Forgetting value range and allocating too small count array.
- Accidentally counting <= instead of strictly <.

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

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] freq = new int[101];
        for (int x : nums) freq[x]++;

        int[] less = new int[101];
        int running = 0;
        for (int v = 0; v <= 100; v++) {
            less[v] = running;
            running += freq[v];
        }

        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = less[nums[i]];
        }
        return ans;
    }
}

func smallerNumbersThanCurrent(nums []int) []int {
    freq := make([]int, 101)
    for _, x := range nums {
        freq[x]++
    }

    less := make([]int, 101)
    running := 0
    for v := 0; v <= 100; v++ {
        less[v] = running
        running += freq[v]
    }

    ans := make([]int, len(nums))
    for i, x := range nums {
        ans[i] = less[x]
    }
    return ans
}

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> freq(101, 0), less(101, 0);
        for (int x : nums) freq[x]++;

        int running = 0;
        for (int v = 0; v <= 100; ++v) {
            less[v] = running;
            running += freq[v];
        }

        vector<int> ans;
        ans.reserve(nums.size());
        for (int x : nums) ans.push_back(less[x]);
        return ans;
    }
};

from typing import List

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        freq = [0] * 101
        for x in nums:
            freq[x] += 1

        less = [0] * 101
        running = 0
        for v in range(101):
            less[v] = running
            running += freq[v]

        return [less[x] for x in nums]

var smallerNumbersThanCurrent = function(nums) {
  const freq = new Array(101).fill(0);
  for (const x of nums) freq[x]++;

  const less = new Array(101).fill(0);
  let running = 0;
  for (let v = 0; v <= 100; v++) {
    less[v] = running;
    running += freq[v];
  }

  return nums.map(x => less[x]);
};

中文

题目概述

对数组中每个元素 nums[i]，计算数组里有多少元素严格小于它。

核心思路

本题数值范围很小（0..100），可直接用计数数组。先统计每个值出现次数，再做前缀累计，就能在 O(1) 时间得到任意值对应的“小于它的数量”。

暴力解法与不足

暴力双循环是 O(n²)；排序 + 索引回填是 O(n log n)。在这个范围下，计数前缀法更直接、常数更小。

最优算法步骤

1）统计 freq[0..100]。
2）构建 less[v]，表示严格小于 v 的元素个数。
3）遍历原数组，ans[i] = less[nums[i]]。
4）返回答案。

复杂度分析

时间复杂度：O(n + K)，其中 K=101。
空间复杂度：O(K)（不计输出数组）。

常见陷阱

- 把包含自身频次的前缀和当成答案，导致变成 <=。
- 忘记题目取值范围，数组开小导致越界。
- 比较条件写成小于等于，语义错误。

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

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] freq = new int[101];
        for (int x : nums) freq[x]++;

        int[] less = new int[101];
        int running = 0;
        for (int v = 0; v <= 100; v++) {
            less[v] = running;
            running += freq[v];
        }

        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = less[nums[i]];
        }
        return ans;
    }
}

func smallerNumbersThanCurrent(nums []int) []int {
    freq := make([]int, 101)
    for _, x := range nums {
        freq[x]++
    }

    less := make([]int, 101)
    running := 0
    for v := 0; v <= 100; v++ {
        less[v] = running
        running += freq[v]
    }

    ans := make([]int, len(nums))
    for i, x := range nums {
        ans[i] = less[x]
    }
    return ans
}

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> freq(101, 0), less(101, 0);
        for (int x : nums) freq[x]++;

        int running = 0;
        for (int v = 0; v <= 100; ++v) {
            less[v] = running;
            running += freq[v];
        }

        vector<int> ans;
        ans.reserve(nums.size());
        for (int x : nums) ans.push_back(less[x]);
        return ans;
    }
};

from typing import List

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        freq = [0] * 101
        for x in nums:
            freq[x] += 1

        less = [0] * 101
        running = 0
        for v in range(101):
            less[v] = running
            running += freq[v]

        return [less[x] for x in nums]

var smallerNumbersThanCurrent = function(nums) {
  const freq = new Array(101).fill(0);
  for (const x of nums) freq[x]++;

  const less = new Array(101).fill(0);
  let running = 0;
  for (let v = 0; v <= 100; v++) {
    less[v] = running;
    running += freq[v];
  }

  return nums.map(x => less[x]);
};