[LeetCode] 327. Count of Range Sum

 Problem : https://leetcode.com/problems/count-of-range-sum/

Time Complexity = O ( N ** 2 ). Time Limit Exceeded.

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        N = len(nums)
        
        sums = [0] * (N+1)
        
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
        result = 0
        for i in range(N+1):
            for j in range(i+1, N+1):
                if lower <= sums[j] - sums[i] <= upper:
                    result += 1
        
        return result

Count and merge sort solution:

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        
        def countAndMergeSort(sums, start, end):
            if end - start <= 1: return 0
            mid = start + (end - start) // 2
            
            count = countAndMergeSort(sums, start, mid) + countAndMergeSort(sums, mid, end)
            
            j = k = t = mid
            cache = [0] * (end - start)
            r = 0
            
            for i in range(start, mid):
                while k < end and sums[k] - sums[i] < lower: 
                    k += 1
                while j < end and sums[j] - sums[i] <= upper: 
                    j += 1
                while t < end and sums[t] < sums[i]:
                    cache[r] = sums[t]
                    r += 1
                    t += 1
    
                cache[r] = sums[i]
                r += 1
            
                count += j - k
            
            r = 0
            for i in range(start, t):
                sums[i] = cache[r]
                r += 1
            
            return count
            
        
        
        
        N = len(nums)
        
        sums = [0] * (N+1)    
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
    
        return countAndMergeSort(sums, 0, len(sums))