LeetCode Problem Workspace
Count of Smaller Numbers After Self
Solve the Count of Smaller Numbers After Self problem using binary search and optimized algorithms.
7
Topics
4
Code langs
3
Related
Practice Focus
Hard · Binary search over the valid answer space
Answer-first summary
Solve the Count of Smaller Numbers After Self problem using binary search and optimized algorithms.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Binary search over the valid answer space
In the Count of Smaller Numbers After Self problem, you need to count the number of smaller elements to the right of each number in the array. Efficient solutions leverage binary search and advanced techniques like Merge Sort or Binary Indexed Trees to optimize performance for large arrays.
Problem Statement
Given an integer array nums, you need to return an array counts where counts[i] represents the number of smaller elements to the right of nums[i]. The solution requires careful consideration of time complexity, especially for larger arrays. The challenge is to find an approach that can efficiently handle the input size of up to 100,000 elements.
For example, with nums = [5,2,6,1], the output should be [2,1,1,0]. To the right of 5, there are two smaller elements (2 and 1). To the right of 2, there is one smaller element (1). To the right of 6, there is one smaller element (1), and to the right of 1, there are no smaller elements.
Examples
Example 1
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
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 details omitted.
Example 3
Input: nums = [-1,-1]
Output: [0,0]
Example details omitted.
Constraints
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
Solution Approach
Binary Search with Merge Sort
Use Merge Sort to divide the array and count inversions (smaller elements to the right) while merging. Binary search can help find the correct position for each element during the merge phase.
Binary Indexed Tree (BIT)
A Binary Indexed Tree can efficiently update and query the count of smaller elements as we traverse the array. This allows for fast updates and queries, reducing the time complexity of the brute-force approach.
Segment Tree
Segment Trees can be used as a variant of BIT to efficiently handle range queries and updates. This is a more complex, but scalable, solution for larger input sizes.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity for this problem depends on the chosen approach. Merge Sort with binary search has a time complexity of O(n log n), where n is the length of the input array. Binary Indexed Tree and Segment Tree approaches also have time complexities of O(n log n) for both time and space, making them suitable for large input sizes.
What Interviewers Usually Probe
- The candidate demonstrates understanding of binary search in the context of array manipulation.
- The candidate can efficiently combine Divide and Conquer strategies with advanced data structures like BIT or Segment Tree.
- The candidate effectively chooses an optimal approach based on problem constraints.
Common Pitfalls or Variants
Common pitfalls
- Failing to recognize that a brute-force solution is too slow for large inputs.
- Misunderstanding the need for sorting or binary search when counting smaller elements.
- Incorrectly implementing the tree or merge phase, resulting in inaccurate counts.
Follow-up variants
- Using Merge Sort with a slight variation to track the counts of smaller numbers while merging.
- Employing Binary Indexed Tree (BIT) for an optimized solution, considering different update/query strategies.
- Using Segment Tree for efficient range queries and handling larger arrays more efficiently.
FAQ
What is the most efficient way to solve the Count of Smaller Numbers After Self problem?
The most efficient solution combines Binary Search with Merge Sort or utilizes a Binary Indexed Tree (BIT) for optimal time complexity of O(n log n).
How do binary search and merge sort work together in this problem?
Binary search is used during the merge step of Merge Sort to determine the position of elements, counting smaller numbers as the array is merged.
Why is a brute-force solution inefficient for large inputs?
A brute-force solution checks every pair of elements, leading to O(n^2) time complexity, which is too slow for arrays of size up to 100,000.
How does a Binary Indexed Tree (BIT) solve this problem?
A BIT allows efficient updates and queries for the count of smaller numbers while traversing the array, reducing the time complexity to O(n log n).
What are the trade-offs between using a Segment Tree versus a Binary Indexed Tree?
A Segment Tree is more flexible and can handle more complex queries, but it’s generally more complex to implement than a Binary Indexed Tree (BIT), which is simpler but less flexible.
Solution
Solution 1
#### Python3
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
alls = sorted(set(nums))
m = {v: i for i, v in enumerate(alls, 1)}
tree = BinaryIndexedTree(len(m))
ans = []
for v in nums[::-1]:
x = m[v]
tree.update(x, 1)
ans.append(tree.query(x - 1))
return ans[::-1]Solution 2
#### Python3
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
alls = sorted(set(nums))
m = {v: i for i, v in enumerate(alls, 1)}
tree = BinaryIndexedTree(len(m))
ans = []
for v in nums[::-1]:
x = m[v]
tree.update(x, 1)
ans.append(tree.query(x - 1))
return ans[::-1]Solution 3
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
alls = sorted(set(nums))
m = {v: i for i, v in enumerate(alls, 1)}
tree = BinaryIndexedTree(len(m))
ans = []
for v in nums[::-1]:
x = m[v]
tree.update(x, 1)
ans.append(tree.query(x - 1))
return ans[::-1]Continue Topic
array
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
Binary search over the valid answer space
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Hard
Stay on this level to stabilize interview delivery.
arrow_forward