327.Count of Range Sum

Tags: [sort], [merge_sort], [divide_conquer], [trick]

Com: {g}

Hard: [####]

Link: https://leetcode.com/problems/count-of-range-sum/\#/description

Given an integer array nums, return the number of range sums that lie in[lower, upper]inclusive.
Range sumS(i, j)is defined as the sum of the elements in numsbetween indices iand j(i≤j), inclusive.

Note:
A naive algorithm ofO(n2) is trivial. You MUST do better than that.

Example:
Given nums =[-2, 5, -1],lower=-2,upper=2,
Return3.
The three ranges are :[0, 0],[2, 2],[0, 2]and their respective sums are:-2, -1, 2.

Solution: Merge Sort, Divide And Conquer

class Solution(object):
    def countRangeSum(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        if not nums:
            return 0

        size = len(nums)
        pre_sum = [0 for _ in xrange(size)]
        pre_sum[0] = nums[0]
        for i in xrange(1, size):
            pre_sum[i] = pre_sum[i - 1] + nums[i]

        return self.count_and_merge_sort(pre_sum, 0, size - 1, lower, upper)

    def count_and_merge_sort(self, pre_sum, start, end, lower, upper):
        # base case
        if start == end:
            return 1 if lower <= pre_sum[start] <= upper else 0

        # the reason why in each level of recursion, we can calculate the counter, and there won't be overlapping calculation:
        # For example, 
        # nums = [1, 2, 3, 4], lower = -2, upper = 7, the pre_sum = [1, 3, 6, 10], 
        # each time we divide the pre_sum into two parts:
        # level1: [1, 3, 6, 10]
        # level2: [1, 3], [6, 10]
        # level3: [1], [3], [6], [10]
        # At each level, we try to use the right part elements(pre_sum) to minus the left part elements(pre_sum)
        # And the result of the current level will become either left part of right part of the upper level, 
        # The algorightm will merge the current level left and right together and 'transfer' to upper level.
        # On the upper level, the the current level's result will become either the left part or the right part.
        # And on each level, we always the right part elements minus the left part elements, 
        # so there won't exist overlapping calculation.

        mid = start + (end - start) / 2
        counter = self.count_and_merge_sort(pre_sum, start, mid, lower, upper) +\
                  self.count_and_merge_sort(pre_sum, mid + 1, end, lower, upper)

        left = pre_sum[start:mid + 1]
        right = pre_sum[mid + 1:end + 1]

        # count
        # The time complexity of counting part is O(n),
        # because left is sorted and right is also sorted.
        # Althougth there are two inner while loop, but we are trying to find
        # lower <= right[r_left] - left[l] <= right[r_right] - left[l] <= upper.
        # So as the l move to right side, the left[l] become bigger and bigger, 
        # if we still want to keep the range(mentioned above), 
        # we need to move both r_left and r_right to right side, 
        # and as the l move to right side, the r_left and r_right always be moved to right side, never went back.
        # So the time complexity of coounting part = O(n). 
        # In short, 
        # as the l move to right side, the r_left and r_right in the inner while loop never move back, always to right side.
        r_left = 0
        r_right = 0
        for l in xrange(len(left)):
            # find the first r_left, which make right[r_left] - left[l] >= lower
            while r_left < len(right) and right[r_left] - left[l] < lower:
                r_left += 1

            # find the first r_right, which make right[r_right] - left[l] > upper
            while r_right < len(right) and right[r_right] - left[l] <= upper:
                r_right += 1

            if r_right - r_left > 0:
                counter += r_right - r_left

        # merge
        ret = []
        l = 0
        r = 0
        while l < len(left) and r < len(right):
            if left[l] == right[r]:
                ret.append(left[l])
                ret.append(right[r])
                l += 1
                r += 1
            elif left[l] < right[r]:
                ret.append(left[l])
                l += 1
            else:
                ret.append(right[r])
                r += 1

        ret += left[l:]
        ret += right[r:]

        # modify the pre_sum in place.
        for i in xrange(len(ret)):
            pre_sum[i + start] = ret[i]

        return counter

Revelation:

• 不会存在重复计算counter的原因：在当前level，我们总是用right part的element去减去left part的element，在当前level结束前我们把left part和right part的elements merge到一起，最为向上一层level的left part 或 right part (只作为上一层left或right的其中一边)， 而我们知道我们是不会去对left part或right part 内部互相减的，所以不会存在重复计算counter的情况.
• count part 的time complexity = O(n) 的原因：left part是sorted的，right part是sorted的，在每一层我们iterate 每一个left element 试图找到 一组r_left, r_right使得 lower <= right[r_left] - left[l] <= right[r_right] - left[l] <= upper，我们每次向右移动 left 的index，因为right是sorted，又因为我们要维护这个range，所以当left index 向右移动时，r_left, r_right 势必不能想左移动，所以看似我们在for loop中有while loop，但其实while loop是一直向右走的，不会往回走，所以T = O(n).

Note:

• Time complexity = O(ngln), n is the number of elements of the given nums.