Watch 10 video solutions for Count of Smaller Numbers After Self, a hard level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by Ayushi Sharma has 34,696 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
Example 2:
Input: nums = [-1] Output: [0]
Example 3:
Input: nums = [-1,-1] Output: [0,0]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104Problem Overview: Given an integer array nums, compute how many smaller elements appear to the right of every index. For each position i, you need the count of numbers nums[j] such that j > i and nums[j] < nums[i]. The output is an array where each value represents that count.
Approach 1: Binary Indexed Tree (Fenwick Tree) (Time: O(n log n), Space: O(n))
This approach processes the array from right to left and uses a Binary Indexed Tree to maintain frequencies of numbers seen so far. Because values may be large or negative, the first step is coordinate compression: map each number to a rank in a sorted order. For every element, query the Fenwick Tree for the prefix sum of ranks smaller than the current value. That prefix sum equals the number of smaller elements already processed (which are to the right in the original array). After the query, update the tree with the current element's rank. Both query and update operations run in O(log n), giving a total complexity of O(n log n).
Approach 2: Divide and Conquer with Binary Search Tree (Time: O(n log n) average, Space: O(n))
This approach builds a Binary Search Tree while scanning the array from right to left. Each node stores the value, the number of nodes in its left subtree, and a duplicate count. When inserting a new number, traverse the tree and accumulate counts: moving right means all nodes in the current node's left subtree plus duplicates are smaller than the inserted value. Moving left increments the left subtree count because a new smaller element is added. The final accumulated value becomes the answer for that index. On average the insertion cost is O(log n), producing O(n log n) overall time, though the worst case can degrade to O(n²) if the tree becomes skewed.
Both solutions rely on efficient counting structures rather than comparing each pair of elements. Problems like this commonly appear in advanced array counting tasks alongside techniques such as merge sort inversion counting and segment trees.
Recommended for interviews: The Fenwick Tree solution is usually the strongest answer. It guarantees O(n log n) time, avoids worst‑case degradation, and demonstrates knowledge of prefix-sum data structures. Explaining the BST method still shows strong reasoning about ordered structures and incremental counting, but interviewers generally prefer Fenwick Tree or merge‑sort based counting because the complexity remains predictable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Best general solution with guaranteed performance and efficient prefix queries. |
| Binary Search Tree Counting | O(n log n) average, O(n²) worst | O(n) | Useful when demonstrating ordered set or BST augmentation techniques. |