Count of Smaller Numbers After Self
Problem
nums. Build and return a list
counts of the same length where counts[i] is how many elements
to the right of index i are strictly smaller than
nums[i].nums = [5,2,6,1]Output[2,1,1,0]nums = [-1]Output[0]nums = [-1,-1]Output[0,0]1 ≤ n ≤ 105 · -104 ≤ nums[i] ≤ 104
Try it yourself
class Solution {
public List<Integer> countSmaller(int[] nums) {
}
}
nums[i] is a single prefix-sum query over smaller
ranks.Instinct Range sums, mins or counts asked again and again while values keep changing: prefix sums break, so reach for a Fenwick or segment tree.
Memory hack Prefix sums freeze, trees breathe: climb by the last set bit (i & -i) for Fenwick, split in halves for segment trees.
Open the Fenwick & Segment Tree guide →Approaches
Brute ForceCompare Every Pair
O(n²)Space O(1) extraFor each index i, scan every j > i and count the
values below nums[i]. This is the definition turned straight into
two loops.
public List<Integer> countSmaller(int[] nums) { int n = nums.length; List<Integer> res = new ArrayList<>(n); for (int i = 0; i < n; i++) { int cnt = 0; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[i]) cnt++; } res.add(cnt); } return res; }
Obviously correct, but ~5·109 comparisons at n = 105.
BetterSorted Suffix + Binary Search Insertion
O(n²) worst (O(n log n) compares)Space O(n)Scan from the right and keep the suffix seen so far in a sorted list.
The lower-bound position of nums[i] in that list equals the number
of smaller values to its right; then insert nums[i] at that position
to keep the list sorted.
public List<Integer> countSmaller(int[] nums) { int n = nums.length; Integer[] res = new Integer[n]; List<Integer> sorted = new ArrayList<>(); // values to the right, ascending for (int i = n - 1; i >= 0; i--) { int pos = lowerBound(sorted, nums[i]); // # of values < nums[i] res[i] = pos; sorted.add(pos, nums[i]); } return Arrays.asList(res); } private int lowerBound(List<Integer> list, int target) { int lo = 0, hi = list.size(); while (lo < hi) { int mid = (lo + hi) >>> 1; if (list.get(mid) < target) lo = mid + 1; else hi = mid; } return lo; }
Searching is logarithmic, but each insert shifts up to n elements.
OptimalFenwick Tree over Value Ranks
O(n log n)Space O(n)Compress values to ranks 1..m. Scanning right to left, a Fenwick
tree holds how many seen values have each rank, so “how many smaller”
is the prefix sum up to rank - 1. Both the query and the
“add one at this rank” update cost O(log m).
public List<Integer> countSmaller(int[] nums) { int n = nums.length; int[] vals = Arrays.stream(nums).distinct().sorted().toArray(); int[] tree = new int[vals.length + 1]; // 1-based Fenwick tree of counts Integer[] res = new Integer[n]; for (int i = n - 1; i >= 0; i--) { int rank = Arrays.binarySearch(vals, nums[i]) + 1; res[i] = prefix(tree, rank - 1); // seen values with a smaller rank for (int k = rank; k < tree.length; k += k & -k) tree[k]++; } return Arrays.asList(res); } private int prefix(int[] tree, int i) { int sum = 0; for (; i > 0; i -= i & -i) sum += tree[i]; return sum; }
Dry runnums = [5,2,6,1]
- start0000ranks of 1,2,5,6
- i=3 (1)1r000prefix(0)=0
- i=2 (6)1001rprefix(3)=1
- i=1 (2)11r01prefix(1)=1
- i=0 (5)111r1prefix(2)=2 ✔
Guaranteed O(n log n) with tiny constants and only a couple of int arrays.
nums[i] + 10001 as the index; a merge-sort that tracks original
indices is the other classic O(n log n) answer.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Compare Every Pair | O(n²) | O(1) extra |
| Better | Sorted Suffix + Binary Search Insertion | O(n²) worst (O(n log n) compares) | O(n) |
| Optimal | Fenwick Tree over Value Ranks | O(n log n) | O(n) |
- Counting smaller or equal — query rank
- 1, not the rank itself. - Scanning left to right — then the tree holds the prefix, not the elements after self.
- Negative values used directly as Fenwick indices — compress or offset first.
- Reframe it: “for each element, count smaller among the ones already processed”.
- Explain why the sorted-list idea is still quadratic (insert shifts), motivating the BIT.
- Mention merge sort with index tracking as an equally valid O(n log n) alternative.