How hard is LeetCode 315. Count of Smaller Numbers After Self?

LeetCode 315. Count of Smaller Numbers After Self is rated Hard on LeetCode.

Count of Smaller Numbers After Self — LeetCode 315 Python Solution

HardBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort

Problem: #315
Pattern: Monotonic Stack
Reading time: 6 min
Source: leetcode.com

The problem

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

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).

Python solution

Python

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]

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 315. Count of Smaller Numbers After Self is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 315. Count of Smaller Numbers After Self?: LeetCode 315. Count of Smaller Numbers After Self is rated Hard on LeetCode.
What topics does LeetCode 315. Count of Smaller Numbers After Self cover?: LeetCode 315. Count of Smaller Numbers After Self is tagged Binary Indexed Tree, Segment Tree, Array, Binary Search, Divide and Conquer, Ordered Set and Merge Sort on LeetCode.