38 · Segment Trees, Fenwick & String Matching
#315 Count of Smaller Numbers After Self
the problem
In plain words
For each index i, count how many elements to the right of i are strictly smaller than nums[i]. Return the counts as a list.
in nums = [5,2,6,1]
out [2,1,1,0]
Right of 5: 2 and 1 are smaller. Right of 2: only 1. Right of 6: only 1.
in nums = [-1]
out [0]
in nums = [-1,-1]
out [0,0]
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFenwick tree (BIT)Merge sort & merging sorted runs
Walk from right to left. Everything already seen is to the right. "How many seen values are smaller than x?" is a prefix count over ranks — exactly what a Fenwick tree answers in O(log n).
solutions
From brute force to optimal
For each i, scan j > i and count smaller values.
- Two nested loops.
- Count nums[j] < nums[i].
n(n−1)/2 pairs — ~5·10⁹ for n = 10⁵, far too slow.
Only the output list.
class Solution { public List<Integer> countSmaller(int[] nums) { List<Integer> result = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { int count = 0; for (int j = i + 1; j < nums.length; j++) if (nums[j] < nums[i]) count++; result.add(count); } return result; }}During merging, each left-half element is passed by exactly the smaller right-half elements that came from its right.
- Sort an array of indices by value using merge sort.
- While merging, count right-half elements taken before each left element.
- Add that count to counts[original index].
Standard merge sort; counting is O(1) per merge step.
Index array, temp buffer, recursion depth O(log n).
class Solution { private int[] counts; public List<Integer> countSmaller(int[] nums) { int n = nums.length; counts = new int[n]; int[] idx = new int[n]; // sort indices, not values, so each count lands on the right element for (int i = 0; i < n; i++) idx[i] = i; sort(nums, idx, new int[n], 0, n - 1); List<Integer> result = new ArrayList<>(n); for (int c : counts) result.add(c); return result; } private void sort(int[] nums, int[] idx, int[] tmp, int lo, int hi) { if (lo >= hi) return; int mid = (lo + hi) >>> 1; sort(nums, idx, tmp, lo, mid); sort(nums, idx, tmp, mid + 1, hi); int i = lo, j = mid + 1, k = lo, smallerFromRight = 0; while (i <= mid && j <= hi) { if (nums[idx[j]] < nums[idx[i]]) { smallerFromRight++; // a right-half value jumps ahead of the left ones tmp[k++] = idx[j++]; } else { counts[idx[i]] += smallerFromRight; // every jumper so far is smaller and was to its right tmp[k++] = idx[i++]; } } while (i <= mid) { counts[idx[i]] += smallerFromRight; tmp[k++] = idx[i++]; } while (j <= hi) tmp[k++] = idx[j++]; System.arraycopy(tmp, lo, idx, lo, hi - lo + 1); }}Map values to ranks, walk right→left, query the count of smaller ranks, then add the current rank.
- sorted = distinct values in order; rank = binarySearch + 1.
- For i from n−1 down to 0: counts[i] = prefix(rank − 1).
- Then add 1 at rank.
Sorting for compression, then two O(log n) Fenwick operations per element.
Sorted ranks, the tree and the output.
class Solution { public List<Integer> countSmaller(int[] nums) { int n = nums.length; int[] sorted = Arrays.stream(nums).distinct().sorted().toArray(); // value -> rank int[] tree = new int[sorted.length + 1]; // counts how many of each rank we have seen Integer[] result = new Integer[n]; for (int i = n - 1; i >= 0; i--) { // walk right to left int rank = Arrays.binarySearch(sorted, nums[i]) + 1; // 1-based rank int smaller = 0; for (int r = rank - 1; r > 0; r -= r & -r) smaller += tree[r]; // seen with a lower rank result[i] = smaller; for (int r = rank; r < tree.length; r += r & -r) tree[r]++; // mark this value as seen } return Arrays.asList(result); }}Dry run
in the room
How to say it in the interview
talk track
- Start with O(n²), then say: "the right-hand side grows one element at a time — I need a structure that inserts and counts smaller values fast."
- Name the options: balanced BST with sizes, merge sort, Fenwick over ranks. Pick Fenwick for short, safe code.
- Explain compression: values can be negative, so ranks keep the tree small and the indices positive.
traps
- Counting ≤ instead of < : query prefix(rank − 1), not prefix(rank).
- Walking left to right — then you'd be counting smaller elements before each index.
what they ask next
Follow-ups
Count inversions in the whole array?
Sum the answer list, or count during merge sort directly — O(n log n).
Reverse Pairs (LC 493): nums[i] > 2·nums[j]?
Same right-to-left Fenwick idea, but query the rank of the largest value < nums[i] / 2 — or count with two pointers during merge sort. Watch out for overflow: use long for 2·nums[j].
before you submit
Edge cases to test
- Equal values are not smaller: [2, 0, 1, 0, 2] → [3, 0, 1, 0, 0]
- One element → [0]
- Strictly decreasing input → [n − 1, …, 1, 0]
- Negative values and the extremes −10⁴ and 10⁴
practise next
Similar problems
- #493Reverse PairsHardin Sorting
- #912Sort an ArrayMediumin Sorting
- #307Range Sum Query - MutableMediumin Range Queries & Strings