315. Count of Smaller Numbers After Self

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Python

Brute Force (Timelimit Exceed)

Time: O(N^2) Space: O(N)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        mapper = []
        for i in range(len(nums)):
            count = 0
            for j in range(i+1, len(nums)):
                if nums[j] < nums[i]:
                    count += 1
            mapper.append(count)
        return mapper

Segment Tree

M = 2 * (10**4)

Time: O(NlogM) Space: O(M)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        size = 2 * 10**4 + 1
        tree = [0] * (2*size)

        def update(i, value):
            i += size
            tree[i] += value
            while i > 1:
                i >>= 1
                tree[i] = tree[i*2] + tree[i*2+1]

        def query(left, right):
            left, right = left+size, right+size
            result = 0

            while left < right:
                if left % 2 == 1:
                    result += tree[left]
                    left += 1
                left >>= 1

                if right % 2 == 1:
                    right -= 1
                    result += tree[right]
                right >>= 1

            return result

        offset = 10**4
        ans = []

        for num in reversed(nums):
            ans.append(query(0, num+offset))
            update(num+offset, 1)

        return ans[::-1]

Fenwick Tree

(TODO)