Problem statement

https://leetcode.com/problems/reverse-pairs/

Solution 1

There is solution, using Binary Indexed Tree (BIT). The idea is traverse our nums from the end and add them to our BIT. Let us look at the example [2,4,4,3,5,1]. Let us look at our BIT after each addition. Let us also look at list, which this BIT represents: it will change like this: \([0, 0, 0, 0, 0, 0] \to [1, 0, 0, 0, 0, 0] \to [1, 0, 0, 0, 0, 1] \to [1, 0, 1, 0, 0, 1] \to\) \([1, 0, 1, 0, 1, 1] \to [1, 0, 1, 0, 2, 1] \to [1, 1, 1, 0, 2, 1]\) We can see here for example we have 0 and 2, because we have two equal numbers in our nums. Then for each num we first find the place where num/2 should be if numbers were sorted and took corresponding number from our BIT.

Complexity

It is O(n log n) for time and O(n) for space

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

class Solution:
    def reversePairs(self, nums):
        n = len(nums)
        nums_copy = sorted(nums)
        tree = BIT(n)
        count = 0
        
        for num in reversed(nums):
            count += tree.query(bisect_left(nums_copy, num/2))
            tree.update(bisect.bisect(nums_copy, num), 1)
        return count

Solution 2

Here is very short SortedList solution, with the same complexity.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

from sortedcontainers import SortedList

class Solution:
    def reversePairs(self, nums):
        SList, ans = SortedList(), 0   
        for length, num in enumerate(nums):
            ans += len(SList) - SList.bisect(2*num)
            SList.add(num)       
        return ans

See also problem 0315 Count of Smaller Numbers After Self, 0327 Count of Range Sum. I think any problem of this type with list of numbers nums can be solved either with BST, Segment Tree or BIT. There is also merge sort solution, I did not explored yet.