Count of Smaller Numbers After Self

Hard
621.

Count of Smaller Numbers After Self

Count of Smaller Numbers After Self is a hard coding problem on arrays, divide and conquer and binary indexed tree, asked in Amazon, Google and Uber interviews.

Given an array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than it.

Example 1

Input
nums = [5,2,6,1]
Output
[2,1,1,0]
Explanation
To the right of 5 sit 2 and 1; to the right of 2 sits 1; to the right of 6 sits 1; nothing follows 1.

Example 2

Input
nums = [-1,-1]
Output
[0,0]
Explanation
Equal values do not count — the comparison is strict.

Example 3

Input
nums = [3,2,1]
Output
[2,1,0]

Constraints

  • 1 <= nums.length <= 100000
  • -1000 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count of Smaller Numbers After Self — Problem & Solution

Count of Smaller Numbers After Self solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count of Smaller Numbers After Self is a hard coding problem on arrays, divide and conquer and binary indexed tree, asked in Amazon, Google and Uber interviews.

Problem statement

Given an array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than it.

Example 1

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation: To the right of 5 sit 2 and 1; to the right of 2 sits 1; to the right of 6 sits 1; nothing follows 1.

Example 2

Input: nums = [-1,-1]
Output: [0,0]
Explanation: Equal values do not count — the comparison is strict.

Example 3

Input: nums = [3,2,1]
Output: [2,1,0]

Constraints

  • 1 <= nums.length <= 100000
  • -1000 <= nums[i] <= 1000

Hints for Count of Smaller Numbers After Self

  1. Hint 1

    The O(n²) double loop is the thing to beat.

  2. Hint 2

    Walk right to left and ask: of the values already inserted, how many are strictly smaller than the current one?

  3. Hint 3

    A Fenwick tree over the value range answers that as a prefix sum. Shift the values so the smallest maps to index 1 — a Fenwick tree cannot hold index 0.

How to solve Count of Smaller Numbers After Self

Process the array from right to left, maintaining a frequency table of everything already seen — which is exactly 'everything to the right'. The answer for the current element is the count of stored values strictly below it, a prefix sum a Fenwick tree serves in O(log V).

Approach

  1. Offset every value by +1001 so the range [-1000, 1000] becomes [1, 2001]; a Fenwick tree is 1-indexed and would loop forever on index 0.
  2. Sweep i from n - 1 down to 0. Query the prefix sum up to v - 1 — the number of stored values strictly less than v — and record it.
  3. Insert v into the tree, then continue.
  4. Reverse the collected answers, since they were produced right to left.

Why it works

When index i is processed, the tree holds precisely nums[i+1..n-1], so prefix(v - 1) counts exactly the elements to the right that are strictly smaller. Using v - 1 rather than v is what excludes ties.

Complexity

  • Time — O(n log V)
  • Space — O(V)

Pitfalls

  • Querying prefix(v) counts equal values too and overcounts every duplicate.
  • Forgetting the final reverse returns the answers back to front.
  • Merge sort with an index array is the other standard solution and has the same complexity.

Reference solution

Python

from typing import List

def countSmaller(nums: List[int]) -> List[int]:
    OFF, SIZE = 1001, 2002
    bit = [0] * (SIZE + 1)
    out = []
    for i in range(len(nums) - 1, -1, -1):
        v = nums[i] + OFF
        s = 0
        p = v - 1
        while p > 0:
            s += bit[p]
            p -= p & -p
        out.append(s)
        q = v
        while q <= SIZE:
            bit[q] += 1
            q += q & -q
    out.reverse()
    return out

Java

public static int[] countSmaller(int[] nums) {
    final int OFF = 1001, SIZE = 2002;
    int[] bit = new int[SIZE + 1];
    int n = nums.length;
    int[] out = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int v = nums[i] + OFF;
        int s = 0;
        for (int p = v - 1; p > 0; p -= p & -p) s += bit[p];
        out[i] = s;
        for (int q = v; q <= SIZE; q += q & -q) bit[q]++;
    }
    return out;
}

C++

vector<int> countSmaller(vector<int>& nums) {
    const int OFF = 1001, SIZE = 2002;
    vector<int> bit(SIZE + 1, 0);
    int n = (int) nums.size();
    vector<int> out(n);
    for (int i = n - 1; i >= 0; i--) {
        int v = nums[i] + OFF;
        int s = 0;
        for (int p = v - 1; p > 0; p -= p & -p) s += bit[p];
        out[i] = s;
        for (int q = v; q <= SIZE; q += q & -q) bit[q]++;
    }
    return out;
}

JavaScript

var countSmaller = function(nums) {
    var OFF = 1001, SIZE = 2002;
    var bit = [];
    for (var t = 0; t <= SIZE; t++) bit.push(0);
    var out = [];
    for (var i = nums.length - 1; i >= 0; i--) {
        var v = nums[i] + OFF;
        var s = 0;
        for (var p = v - 1; p > 0; p -= p & -p) s += bit[p];
        out.push(s);
        for (var q = v; q <= SIZE; q += q & -q) bit[q]++;
    }
    out.reverse();
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays