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] <= 104The #315 Count of Smaller Numbers After Self problem asks you to determine, for each element in an array, how many smaller elements appear to its right. A brute force approach compares every pair, but this leads to O(n^2) time and is inefficient for large inputs.
A more optimal strategy uses a modified merge sort. During the merge step, while combining two sorted halves, you track how many elements from the right half move before elements in the left half. These movements directly represent the number of smaller elements appearing after each value. This divide-and-conquer technique efficiently accumulates counts while maintaining sorted order.
Another powerful approach uses a Binary Indexed Tree (Fenwick Tree) or Segment Tree with coordinate compression. By iterating from right to left, you query how many smaller elements have already been inserted and update the structure accordingly.
Both optimized strategies achieve O(n log n) time complexity and are common patterns in advanced interview problems involving inversion counting or order statistics.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Modified Merge Sort | O(n log n) | O(n) |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) |
| Segment Tree | O(n log n) | O(n) |
| Brute Force | O(n^2) | O(1) |
happygirlzt
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.
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.
1import java.util.*;
2
3class Solution {
4 class FenwickTree {
5 private int[] tree;
6This Java solution uses a nested FenwickTree class to manage the BIT operations. We utilize an offset to map negative numbers into a positive index space. For each number, we query the BIT to get the number of smaller elements and then update the BIT with the current number. The result is stored in an Integer list that respects the problem's constraints.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Merge sort naturally divides the array and merges sorted halves. During merging, you can track how many elements from the right side are placed before those from the left, which directly represents the number of smaller elements after each value.
Yes, this problem or its variations are frequently asked in FAANG and other top tech interviews. It tests knowledge of divide and conquer, advanced data structures, and inversion-count style techniques.
Binary Indexed Trees (Fenwick Trees) and Segment Trees are commonly used. With coordinate compression, they allow efficient prefix queries to count how many smaller elements have already appeared while scanning the array from right to left.
The most common optimal solution uses a modified merge sort that counts how many elements from the right subarray move ahead of elements in the left during merging. This allows counting smaller elements after each number in O(n log n) time.
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.