LeetCode 315: Count of Smaller Numbers After Self Solution

Master LeetCode problem 315 (Count of Smaller Numbers After Self), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

315. Count of Smaller Numbers After Self

Hard

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

Problem 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 result of 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 result array.
Return the result array as the final output.

Time Complexity: O(n log n) where n is the length of the input array Space Complexity: O(n)

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 315 (Count of Smaller Numbers After Self)?

This page provides optimized solutions for LeetCode problem 315 (Count of Smaller Numbers After Self) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 315 (Count of Smaller Numbers After Self)?

The time complexity for LeetCode 315 (Count of Smaller Numbers After Self) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 315 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 315 in Java, C++, or Python.

Back to LeetCode Solutions