1

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

I am just using the merge sort to do this and while doing merging process, I am piggyback checking the condition nums[i] > 2*nums[j]. However, it is timing out for last test case. Help? Link.

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def merge(left, right):
            #print(left, right)
            if not left or not right:
                return (0, left + right)
            #if everything in left is less than right
            left_idx, right_idx, count = 0, 0, 0
            merged_output = []
            while left_idx < len(left) and right_idx < len(right):
                #print(left[left_idx], right[right_idx])
                if left[left_idx] > 2*right[right_idx]:
                    count += len(left) - left_idx
                    right_idx += 1
                else:
                    left_idx += 1
            left_idx, right_idx = 0, 0
            while left_idx < len(left) and right_idx < len(right):
                if left[left_idx] > right[right_idx]:
                    merged_output += [right[right_idx]]
                    right_idx += 1
                else:
                    merged_output += [left[left_idx]]
                    left_idx += 1
            if left_idx == len(left):
                merged_output += right[right_idx:]
            else:
                merged_output += left[left_idx:]
            return (count, merged_output)

        def partition(nums):
            count = 0
            if len(nums) == 1 or not nums:
                return (0, nums)
            pivot = len(nums)//2
            left_count, l = partition(nums[:pivot])
            right_count, r = partition(nums[pivot:])          
            temp_count, temp_list = merge(l, r)
            #print(temp_count)
            return (count + left_count + right_count + temp_count, temp_list)
        return partition(nums)[0]
noman pouigt
  • 906
  • 11
  • 25
  • If you just count the pairs, this can be solved with a single line of Python code. Did you try such not optimized solution? Does it time-out too? – VPfB Dec 15 '17 at 11:26
  • Have you looked at the various algorithms [here](https://stackoverflow.com/questions/337664/counting-inversions-in-an-array)? – PM 2Ring Dec 15 '17 at 12:09
  • @PM2Ring: yes, so? – noman pouigt Dec 15 '17 at 18:32
  • Your code does not give correct results. You need to change `if left[left_idx] > 2 * right[right_idx]:` to `if left[left_idx] > right[right_idx]:`. Also, that `# check for condition before we merge it` loop slows your code down. FWIW, I've just submitted [an answer](https://stackoverflow.com/a/47845960/4014959) to the linked question which does a timing comparison of all the Python answers there; I included a repaired version of your code in the tests. – PM 2Ring Dec 16 '17 at 13:22
  • @PM2Ring: i have modified the code and now it passes all except last one. – noman pouigt Dec 16 '17 at 20:29

0 Answers0