Count of Smaller Numbers After Self - Solution & Explanation
Problem Statement
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] <= 104
Approach Overview
Problem 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 1: Approach 1: Binary Indexed Tree (Fenwick Tree)
The Binary Indexed Tree (BIT) allows us to efficiently update elements and calculate cumulative frequencies in an iterative manner. In this approach, we traverse the input array from right to left, update the BIT with the index of the current number, and use the BIT to find the count of numbers which are smaller.
This C program uses a static array to represent a Binary Indexed Tree, or Fenwick Tree. It processes each element of the array from right to left and maintains cumulative frequencies of numbers within the bounds. First, it retrieves the cumulative frequency up to one less than the current index using the BIT, which gives the count of numbers less than the current number. Then, it updates the BIT with the frequency of the current number.
Complexity
Time Complexity: O(n log n), where n is the number of elements in nums. Updating the BIT and querying both take O(log n) time.
Space Complexity: O(n) for the BIT and result array.
Approach 2: Approach 2: Divide and Conquer with Binary Search Tree
This approach takes advantage of the divide and conquer strategy combined with a binary search tree (BST). As we process each number from right to left, we insert them into the BST, which allows us to compute the count of elements smaller than the current number efficiently.
The C approach utilizes a binary search tree structure for efficient storage and retrieval of number counts. The insert function adds numbers to the tree while maintaining information about left and right subtree node counts. This allows quick determination of how many smaller elements precede the current number.
Complexity
Time Complexity: O(n log n) on average, assuming balanced inserts into the BST.
Space Complexity: O(n) for storing BST nodes and result array.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Indexed Tree (Fenwick Tree) | Time Complexity: O(n log n), where n is the number of elements in |
| Approach 2: Divide and Conquer with Binary Search Tree | Time Complexity: O(n log n) on average, assuming balanced inserts into the BST. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Count of Smaller Numbers After Self | Leetcode June Challenge | Leetcode 315 | C++ | Approach + Code • Ayushi Sharma • 35,471 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count of Smaller Numbers After Self easy or hard?
Count of Smaller Numbers After Self Python or Java solution?
How to solve Count of Smaller Numbers After Self in O(n log n)?
What is the best approach for Count of Smaller Numbers After Self?
Is Count of Smaller Numbers After Self asked at Google/Amazon/Meta?
What data structure is used in Count of Smaller Numbers After Self?
What is the time complexity of Count of Smaller Numbers After Self?
Ready to solve this problem?
Practice Count of Smaller Numbers After Self with our built-in code editor and test cases.
Practice on FleetCode