HardArrayBinary Indexed TreeMerge SortDivide and Conquer

Count of Smaller Numbers After Self

1 approach, code in every language

For each position in an integer array, determine how many values located strictly to its right are smaller than the value at that position. Return these tallies as an array aligned with the original positions.

A brute-force double loop is quadratic, which is too slow for large inputs. Processing the array from right to left while maintaining an order-statistics structure lets each query answer 'how many already-seen values are smaller' in logarithmic time.

Example 1

Input: nums = [5,2,6,1]

Output: [2,1,1,0]

To the right of 5 there are two smaller values (2 and 1); to the right of 2 there is one (1); to the right of 6 there is one (1); and the last element has nothing after it.

Example 2

Input: nums = [-1,-1]

Output: [0,0]

Neither element has a strictly smaller value to its right.

Constraints

1 ≤ nums.length ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4

Coordinate Compression + Fenwick Tree

Map values to compact ranks, then scan right to left, using a Fenwick tree to count how many previously inserted values have a smaller rank before inserting the current value.

Loading animation…

Intuition

Reading the array from the back means everything already inserted into the tree lies to the right of the current element. The question 'how many are smaller' becomes 'how many inserted ranks are below my rank', which a Fenwick tree answers as a prefix sum of counts. Compressing the raw values to consecutive ranks keeps the tree small even when values are sparse or negative, and each insertion and query costs only logarithmic time.

Algorithm walkthrough

1Sort the distinct values and assign each a 1-based rank so lookups map any value to a small index.
2Create a Fenwick tree of counts sized to the number of distinct values.
3Traverse the array from the last element to the first. For the current value, query the tree for the total count of ranks strictly below its rank; that is its answer.
4Insert the current value by adding one at its rank in the tree.
5Return the answers array once the traversal completes.

Implementation

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sorted_unique = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
        m = len(sorted_unique)
        tree = [0] * (m + 1)

        def update(i: int) -> None:
            while i <= m:
                tree[i] += 1
                i += i & (-i)

        def query(i: int) -> int:
            s = 0
            while i > 0:
                s += tree[i]
                i -= i & (-i)
            return s

        result = [0] * len(nums)
        for idx in range(len(nums) - 1, -1, -1):
            r = rank[nums[idx]]
            result[idx] = query(r - 1)
            update(r)
        return result

Time

O(n log n)

Space

O(n)

Sorting for compression plus n Fenwick updates and queries.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Cooler Gauges Downstream is our own problem on the technique behind Count of Smaller Numbers After Self: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free