Count of Smaller Numbers After Self
Hard Merge sort with indexes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For every element, count how many elements to its right are strictly smaller.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each number, how many to its right are smaller?
Why this works: during merge sort, when a left element is placed, every right element already placed is smaller and was to its right. Add that count.
Example: [5, 2, 6, 1]
5 → (2, 1) = 22 → (1) = 16 → (1) = 11 → 0 → [2, 1, 1, 0]
✦Hints open one at a time
↗Approach
Merge sort an index array by value. While merging, keep rightTaken = how many right-half elements were placed so far. When a left element is placed, add rightTaken to its count. Take from the left on ties so equal values aren't counted.
</>Solution (Java)
import java.util.*;
class Solution {
private int[] counts, idx, tmp, nums;
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
this.nums = nums;
counts = new int[n];
idx = new int[n];
tmp = new int[n];
for (int i = 0; i < n; i++) idx[i] = i;
sort(0, n - 1);
List<Integer> res = new ArrayList<>();
for (int c : counts) res.add(c);
return res;
}
private void sort(int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
sort(lo, mid);
sort(mid + 1, hi);
int i = lo, j = mid + 1, k = lo, rightTaken = 0;
while (i <= mid && j <= hi) {
if (nums[idx[j]] < nums[idx[i]]) {
rightTaken++; // a smaller element from the right
tmp[k++] = idx[j++];
} else {
counts[idx[i]] += rightTaken;
tmp[k++] = idx[i++];
}
}
while (i <= mid) {
counts[idx[i]] += rightTaken;
tmp[k++] = idx[i++];
}
while (j <= hi) tmp[k++] = idx[j++];
System.arraycopy(tmp, lo, idx, lo, hi - lo + 1);
}
}!Common mistake
Sorting the values directly — you lose track of which original position each count belongs to.
- Time: O(n log n).
- Space: O(n).