LeetCode 315: Count of Smaller Numbers After Self
LeetCode 315 Solution Explanation
Explanation:
To solve this problem, we can use the concept of Binary Indexed Tree (Fenwick Tree). We will iterate through the given array from right to left and update the Binary Indexed Tree for each element. The Binary Indexed Tree helps us efficiently calculate the count of smaller numbers to the right of a particular element.
Here's the step-by-step algorithm:
- Create a Binary Indexed Tree (Fenwick Tree) of size equal to the maximum element in the given array.
- Initialize an array
resultof the same size as the input array to store the count of smaller numbers after each element. - Iterate through the input array in reverse order:
- For each element, query the Binary Indexed Tree to get the count of smaller elements than the current element.
- Update the Binary Indexed Tree by incrementing the count at the index corresponding to the current element.
- Store the count in the
resultarray.
- Return the
resultarray as the final output.
Time Complexity: O(n log n) where n is the length of the input array Space Complexity: O(n)
:
LeetCode 315 Solutions in Java, C++, Python
class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<>();
int offset = 10000; // Offset to handle negative numbers
int[] fenwickTree = new int[2 * offset + 2];
for (int i = nums.length - 1; i >= 0; i--) {
int smallerCount = query(fenwickTree, nums[i] + offset);
result.add(smallerCount);
update(fenwickTree, nums[i] + offset + 1, 1);
}
Collections.reverse(result);
return result;
}
private void update(int[] fenwickTree, int index, int value) {
while (index < fenwickTree.length) {
fenwickTree[index] += value;
index += index & -index;
}
}
private int query(int[] fenwickTree, int index) {
int count = 0;
while (index > 0) {
count += fenwickTree[index];
index -= index & -index;
}
return count;
}
}Interactive Code Editor for LeetCode 315
Improve Your LeetCode 315 Solution
Use the editor below to refine the provided solution for LeetCode 315. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...