HardNeetCode150ArrayBinary SearchDivide and ConquerSegment TreeBinary Indexed TreeMerge SortOrdered Set
Count of Smaller Numbers After Self
Count smaller elements to the right.
Examples
Input
nums = [5,2,6,1]
Output
[2,1,1,0]
2 smaller after 5, 1 after 2, 1 after 6, 0 after 1.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^4 <= nums[i] <= 10^4
Approaches
Count for each element.
CodeT: O(n^2) | S: O(n) output space
Count during merge.
CodeT: O(n log n) | S: O(n) temp array
Fenwick tree for counts.
CodeT: O(n log n) | S: O(n) BIT
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) output space | Count for each element. |
| Merge Sort | O(n log n) | O(n) temp array | Count during merge. |
| Binary Indexed Tree | O(n log n) | O(n) BIT | Fenwick tree for counts. |
Brute Force
T: O(n^2)S: O(n) output space
Count for each element.
Merge Sort
T: O(n log n)S: O(n) temp array
Count during merge.
Binary Indexed Tree
T: O(n log n)S: O(n) BIT
Fenwick tree for counts.
Common Mistakes
Not handling duplicates
Wrong merge count
Off-by-one in BIT