The ingenuity of the problem comes from the fact that we need a separate while loop to get the inversion count. This is due to the condition for moving the left and right pointer is different than the merge step of the problem. In the count inversion where left is simply greater than right, the condition to increment counter and movement of left and right pointer were overlapping, hence both could be done in the same loop. Hence for this problem, the merge step needs two iterations instead of one.
class Solution:
def merge(self, nums: list[int], s: int, m: int, e: int) -> int:
cnt: int = 0
if s >= e:
return cnt
l, r = s, m + 1
while l <= m and r <= e:
if nums[l] > 2 * nums[r]:
cnt += m - l + 1
r += 1
else:
l += 1
temp: list[int] = []
l, r = s, m + 1
while l <= m and r <= e:
if nums[l] <= nums[r]:
temp.append(nums[l])
l += 1
else:
temp.append(nums[r])
r += 1
temp.extend(nums[l : m + 1])
temp.extend(nums[r : e + 1])
nums[s : e + 1] = temp
return cnt
def mergeSort(self, nums: list[int], s: int, e: int) -> int:
cnt: int = 0
if s >= e:
return cnt
m: int = s + ((e - s) >> 1)
cnt += self.mergeSort(nums, s, m)
cnt += self.mergeSort(nums, m + 1, e)
cnt += self.merge(nums, s, m, e)
return cnt
def reversePairs(self, nums: list[int]) -> int:
n: int = len(nums)
res: int = self.mergeSort(nums, 0, n - 1)
return res