The tricky part: coordinate compression must include both and values.
function reversePairs(nums):
// Collect all values needed
all_vals = set of all values in nums
for x in nums:
all_vals.add(2 * x)
sorted_vals = sorted list of all_vals
rank = map each value v to its 1-based position in sorted_vals
n = sorted_vals.length
tree = array of size (n + 1), filled with 0
result = 0
for num in nums from right to left:
// Query: how many 2*elem values in tree are < num
r = rank[num]
result += query(r - 1)
// Update: add 2*num for future left-side queries
update(rank[2 * num])
return result
Process right to left. For each , query how many values (from elements to its right) fall below . Time: . Space: .