493. Reverse Pairs

Given an arraynums, we call(i, j)animportant reverse pairifi < jandnums[i] > 2*nums[j].

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

Example1:

Input: [1,3,2,3,1]

Output: 2

Example2:

Input: [2,4,3,5,1]

Output: 3

Note:

  1. The length of the given array will not exceed 50,000.
  2. All the numbers in the input array are in the range of 32-bit integer.

Thoughts:

  1. Implementation of BST (Binary Search Tree):

    1. Node { val, cnt (sub-problem result), left, right}

    2. for each element in the nums: perform search and insert: search element >= 2nums[i] + 1 from the root, and insert val into the root.

    3. implementation of search:

      1. if root is none -> return
      2. if val < root.val -> meaning hitting the upper bound -> return root.cnt + search (root.left, val)
      3. if val == root.val -> return root.cnt
      4. if val > root.val -> meaning current root.val in not the upper bound -> search (root.right, val)

    4. T: O(nlogn) - O(n^2)

  2. Implementation of BIT (Binary Indexed Tree):

    1. Sort the original array into a copy

    2. For each element in the original array sequentially:

      1. Using binary search to find corresponding index in the sorted array from the element in the original array

      2. Search in the BIT and then Insert the entry into BIT

  3. Implementation of Merge Sort:

    1. For partition recurrence relation, settingi = 0, j = n - 1, m = (n-1)/2, we have:T(0, n - 1) = T(0, m) + T(m + 1, n - 1) + C

    2. where the subproblemCnow reads "find the number of important reverse pairs with the first element of the pair coming from the left subarraynums[0, m]while the second element of the pair coming from the right subarraynums[m + 1, n - 1]".

    3. Again for this subproblem, the first of the two aforementioned conditions is met automatically. As for the second condition, we have as usual this plain linear scan algorithm, applied for each element in the left (or right) subarray. This, to no surprise, leads to theO(n^2)naive solution.

    4. Fortunately the observation holds true here that the order of elements in the left or right subarray does not matter, which prompts sorting of elements in both subarrays. With both subarrays sorted, the number of important reverse pairs can be found in linear time by employing the so-called two-pointer technique: one pointing to elements in the left subarray while the other to those in the right subarray and both pointers will go only in one direction due to the ordering of the elements.

    5. The last question is which algorithm is best here to sort the subarrays. Since we need to partition the array into halves anyway, it is most natural to adapt it into aMerge-sort. Another point in favor ofMerge-sortis that the searching process above can be embedded seamlessly into its merging stage.

    6. So here is theMerge-sort-based solution, where the function"reversePairsSub"will return the total number of important reverse pairs within subarraynums[l, r]. The two-pointer searching process is represented by the nestedwhileloop involving variablep, while the rest is the standard merging algorithm.

  4. Reference

Code : BST (LTE) since O(n^2) for data like [1,2,3....]

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        root = None
        for num in nums:
            ans += self.search(root, (num << 1) + 1)
            root = self.insert(root, num)

        return ans

    def search(self, root, val):
        if root is None:
            return 0
        elif val < root.val:
            return root.cnt + self.search(root.left, val)
        elif val == root.val:
            return root.cnt
        else:
            return self.search(root.right, val)

    def insert(self, root, val):
        if root is None:
            root = BSTNode(val)
        elif val < root.val:
            root.left = self.insert(root.left,val)
        elif val == root.val:
            root.cnt+= 1
        else:
            root.cnt+= 1
            root.right = self.insert(root.right, val)
        return root
class BSTNode(object):

    def __init__ (self, val):
        self.val = val
        self.cnt = 1
        self.left = self.right = None

Code : BIT T: O(nlogn)

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def index (arr, val):
            l, r, m = 0, len(arr) - 1, 0
            while(l <= r):
                m = l + ((r - l)>> 1)
                if(arr[m] >= val):
                    r = m - 1
                else: 
                    l = m + 1
            return l + 1
        def search(bit, i):
            s = 0
            while i < len(bit): # this problem asks "greater than", opposite to the conventional BIT
                s += bit [i]
                i += i & -i
            return s 
        def insert(bit, i): # this problem asks "greater than", opposite to the conventional BIT
            while i > 0 : 
                bit[i] += 1
                i -= i& -i
        ans = 0
        bit = [0] * (len(nums) + 1)
        sortedNums = sorted(nums)
        for num in nums:
            ans += search(bit, index(sortedNums, 2L * num + 1))
            insert( bit,  index(sortedNums, num))    
        return ans

Code: Merge-Sort T: O(nlogn)

class Solution {
    public int reversePairs(int[] nums) {
        return reversePairsHelper(nums, 0, nums.length - 1);
    }

    private int reversePairsHelper(int [] nums, int l, int r){
        if(l >= r ) return 0;

        int m = l + ((r - l) >> 1);
        int ans = reversePairsHelper(nums, l, m) + reversePairsHelper(nums, m + 1, r);

        int left = l, right = m + 1, i = 0, pair = m + 1;
        int [] merge = new int[r - l + 1];

        while(left <= m){
            // search
            while(pair <= r && nums[left] > 2L * nums[pair]) pair++;
            ans += pair - (m + 1);

            // merge (insert)

            while(right <= r && nums[left] >= nums[right]) merge[i++] = nums[right++];
            merge[i++] = nums[left++];
        }

        // add the leftover from right to r;
        while(right <= r) merge[i++] = nums[right++];

        System.arraycopy(merge, 0, nums, l, merge.length);

        return ans;
    }

}

results matching ""

    No results matching ""