BinarySearch 0757 Triple Inversion

Problem statement

https://binarysearch.com/problems/Triple-Inversion/

Solution

Solution

Almost the same as Leetcode 0493 Reverse Pairs

Complexity

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

Code

from sortedcontainers import SortedList

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