Log inSign up
hardLeetCodeNot Started

Count of Smaller Numbers After Self

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Example 1 · Example 1:

Input: nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller elements.

Example 2 · Example 2:

Input: nums = [-1]
Output: [0]
Explanation: There are no elements to the right of -1.

Example 3 · Example 3:

Input: nums = [-1, -1]
Output: [0, 0]
Explanation: No element strictly smaller than -1 appears to its right.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Count of Smaller Numbers After Self.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Count of Smaller Numbers After Self
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Constraint sizes where n <= 1000.
  • BETTER: When using standard range frequency templates.
  • OPTIMAL: Gold standard interview solution that avoids any external data structures.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Nested Loops

Intuition

Iterate through each index i from 0 to n - 1. For each i, inner loop through all j > i and increment a counter whenever nums[j] < nums[i]. While trivial to implement, testing all pairs takes O(n2) time, causing TLE when n = 105.

When to apply: Constraint sizes where n <= 1000.

Algorithm

  1. Step 1: Allocate counts array of length n initialized to 0.
  2. Step 2: Loop i from 0 to n - 1.
  3. Step 3: Loop j from i + 1 to n - 1.
  4. Step 4: If nums[j] < nums[i], increment counts[i].
  5. Step 5: Return counts.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4std::vector<int> countSmallerBrute(const std::vector<int>& nums) {
5 int n = nums.size();
6 std::vector<int> counts(n, 0);
7 for (int i = 0; i < n; ++i) {
8 for (int j = i + 1; j < n; ++j) {
9 if (nums[j] < nums[i]) {
10 counts[i]++;
11 }
12 }
13 }
14 return counts;
15}
16
17int main() {
18 std::vector<int> nums = {5, 2, 6, 1};
19 auto res = countSmallerBrute(nums);
20 for (int x : res) std::cout << x << " ";
21 std::cout << std::endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(n^2) where n is nums length
  • Space complexity: O(1) auxiliary space (excluding result array)

2. Binary Indexed Tree (Fenwick Tree) with Coordinate Compression

Intuition

Traversing from right to left ensures that every element inserted into our frequency table is currently to the right of the current element nums[i]. 1. Coordinate compress the elements of nums to map each unique value to a rank 1 \dots M. 2. Initialize a Fenwick tree (BIT) of size M. 3. Iterate i backwards from n - 1 down to 0: - Query the Fenwick tree for the count of items with rank < \text{rank}(nums[i]). - Store this query result into \text{counts}[i]. - Insert +1 at \text{rank}(nums[i]) in the Fenwick tree. 4. Total runtime is O(n log n) with O(n) space.

When to apply: When using standard range frequency templates.

Algorithm

  1. Step 1: Coordinate compress nums: sort unique values and map each value to rank [1..M].
  2. Step 2: Allocate BIT of size M.
  3. Step 3: Iterate i from n - 1 down to 0.
  4. Step 4: Query BIT sum up to rank(nums[i]) - 1 and record in counts[i].
  5. Step 5: Add 1 to rank(nums[i]) in BIT.
  6. Step 6: Return counts array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct BIT {
6 int n;
7 std::vector<int> tree;
8 BIT(int n) : n(n), tree(n + 1, 0) {}
9 void add(int i, int delta) {
10 for (; i <= n; i += i & -i) tree[i] += delta;
11 }
12 int query(int i) {
13 int sum = 0;
14 for (; i > 0; i -= i & -i) sum += tree[i];
15 return sum;
16 }
17};
18
19std::vector<int> countSmallerBIT(const std::vector<int>& nums) {
20 int n = nums.size();
21 std::vector<int> sortedVals = nums;
22 std::sort(sortedVals.begin(), sortedVals.end());
23 sortedVals.erase(std::unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());
24
25 auto getRank = [&](int val) {
26 return std::lower_bound(sortedVals.begin(), sortedVals.end(), val) - sortedVals.begin() + 1;
27 };
28
29 BIT bit(sortedVals.size());
30 std::vector<int> counts(n);
31
32 for (int i = n - 1; i >= 0; --i) {
33 int r = getRank(nums[i]);
34 counts[i] = bit.query(r - 1);
35 bit.add(r, 1);
36 }
37
38 return counts;
39}
40
41int main() {
42 std::vector<int> nums = {5, 2, 6, 1};
43 auto res = countSmallerBIT(nums);
44 for (int x : res) std::cout << x << " ";
45 std::cout << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(n log n) time
  • Space complexity: O(n) auxiliary space for sorted ranks and Fenwick tree

3. Merge Sort with Index Tracking

Intuition

We can solve this problem elegantly with modified Merge Sort: 1. Maintain an array of indices indices = [0, 1, ..., n - 1]. 2. When merging two sorted subarrays indices[left..mid] and indices[mid+1..right]: - Keep a counter rightCounter representing the number of elements from the right subarray that are strictly smaller than the current left element. - When nums[indices[j]] < nums[indices[i]]: the right element is smaller, so it gets merged first, and we increment rightCounter++. - When nums[indices[i]] <= nums[indices[j]]: the left element is placed next into the merged array. Because exactly rightCounter elements from the right half were smaller than it (and originally appeared to its right!), add rightCounter to counts[indices[i]]. 3. This achieves optimal O(n log n) time with zero coordinate compression and outstanding cache locality.

When to apply: Gold standard interview solution that avoids any external data structures.

Algorithm

  1. Step 1: Initialize indices array [0..n-1] and counts array of size n with 0.
  2. Step 2: Define mergeSort(left, right) dividing indices into left and right halves.
  3. Step 3: Recursively sort left and right halves.
  4. Step 4: Merge both halves with pointers i (left) and j (mid + 1). Maintain rightCounter.
  5. Step 5: If right element is smaller, advance j and increment rightCounter.
  6. Step 6: If left element is smaller or equal, advance i, add rightCounter to counts[indices[i]], and place in temp.
  7. Step 7: Copy merged temp array back into indices.

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initialize indices = [0, 1, 2, 3] representing nums = [5, 2, 6, 1]
Visual state
Values and pointers at this exact step
pointers
S
5
2
6
1
0
↑ left
1
↑ mid
2
3
↑ right
Check / comparison
Split indices into left [0, 1] and right [2, 3]
Decision / next transition
Begin sorting subarrays
Why this step matters

Initialize indices = [0, 1, 2, 3] representing nums = [5, 2, 6, 1]. MergeSort divides into [0, 1] (nums: 5, 2) and [2, 3] (nums: 6, 1).

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5void mergeSort(std::vector<int>& indices, int left, int right, const std::vector<int>& nums,
6 std::vector<int>& counts, std::vector<int>& temp) {
7 if (left >= right) return;
8 int mid = left + (right - left) / 2;
9 mergeSort(indices, left, mid, nums, counts, temp);
10 mergeSort(indices, mid + 1, right, nums, counts, temp);
11
12 int i = left, j = mid + 1, k = left;
13 int rightCounter = 0;
14
15 while (i <= mid && j <= right) {
16 if (nums[indices[j]] < nums[indices[i]]) {
17 rightCounter++;
18 temp[k++] = indices[j++];
19 } else {
20 counts[indices[i]] += rightCounter;
21 temp[k++] = indices[i++];
22 }
23 }
24
25 while (i <= mid) {
26 counts[indices[i]] += rightCounter;
27 temp[k++] = indices[i++];
28 }
29
30 while (j <= right) {
31 temp[k++] = indices[j++];
32 }
33
34 for (int idx = left; idx <= right; ++idx) {
35 indices[idx] = temp[idx];
36 }
37}
38
39std::vector<int> countSmaller(std::vector<int>& nums) {
40 int n = nums.size();
41 std::vector<int> indices(n);
42 std::iota(indices.begin(), indices.end(), 0);
43 std::vector<int> counts(n, 0);
44 std::vector<int> temp(n);
45
46 mergeSort(indices, 0, n - 1, nums, counts, temp);
47 return counts;
48}
49
50int main() {
51 std::vector<int> nums = {5, 2, 6, 1};
52 auto res = countSmaller(nums);
53 for (int x : res) std::cout << x << " ";
54 std::cout << std::endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(n log n) time
  • Space complexity: O(n) auxiliary space for temp merge array and indices

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Nested LoopsO(n^2) where n is nums lengthO(1) auxiliary space (excluding result array)For each element at index i, count elements at indices j > i that are strictly smaller than nums[i].O(n2) where n is nums length
2.Binary Indexed Tree (Fenwick Tree) with Coordinate CompressionO(n log n) timeO(n) auxiliary space for sorted ranks and Fenwick treeTraverse nums from right to left. Query the prefix sum of counts strictly smaller than nums[i] in a Fenwick tree, then insert nums[i].O(n log n) time
3.Merge Sort with Index TrackingOptimalO(n log n) timeO(n) auxiliary space for temp merge array and indicesSort indices of nums via Merge Sort. When an element from the right half is placed before an element from the left half, track how many smaller elements jumped across.O(n log n) time

Common Pitfalls & Crucial Edge Cases

Losing original indices during sorting

When sorting with Merge Sort, you MUST sort pairs {val, originalIndex} to write counts to the correct original positions.

Counting duplicate values as smaller

Condition specifies strictly smaller (nums[j] < nums[i]). Query must be query(rank - 1), not query(rank).

O(N^2) nested loops

Iterating from i + 1 to N takes O(N2) and triggers TLE when N = 105.

Crucial Edge Cases to Validate:

  • Array is strictly ascending `[1, 2, 3, 4]` — Returns [0, 0, 0, 0].
  • Array is strictly descending `[4, 3, 2, 1]` — Returns [3, 2, 1, 0].
  • Array with duplicate values `[5, 2, 6, 1, 1]` — Identical numbers do NOT count as strictly smaller.
  • Single element array `[1]` — Returns [0].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the right-to-left traversal invariant: scanning from right to left naturally restricts the problem to 'elements seen so far'.
  2. Compare the two standard optimal approaches: Merge Sort with indexed pairs vs Fenwick Tree with coordinate compression.
  3. Show how this problem is isomorphic to counting inversions in an array.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does modified Merge Sort solve Count of Smaller Numbers After Self in O(N log N) time?

2.How does a Fenwick Tree (Binary Indexed Tree) solve this problem?

3.Why is coordinate compression needed when using a Fenwick Tree for this problem?

Back to DSA Sheet