Count Of Range Sum - Leetcode Solution

The Count Of Range Sum problem on LeetCode is a bit tricky problem that involves finding the number of range sums within a given range. In this problem, we are given an array of integers and two integers, low and high. The task is to find the number of ranges that exist within the given array whose sum falls within the range of [low, high].

Here is a step-by-step solution to the Count Of Range Sum problem on LeetCode:

Step 1: Preprocessing

The first step is to preprocess the given array and create an array of suffix sums. We can use this suffix sum array to calculate the sum of any subarray in constant time.

Step 2: Divide and conquer

The next step is to use the divide and conquer approach to solve this problem. We can divide the array into two subarrays and recursively count the number of ranges in each subarray. Then, we need to count the number of ranges that cross both subarrays.

Step 3: Counting the number of ranges

To count the number of ranges, we can use a bit of trickery.

We can first calculate the number of ranges in the left subarray and the right subarray. To do this, we need to find the number of pairs of indices i and j such that i < j and prefixSum[j] - prefixSum[i] falls within the range of [low, high].

To count the number of ranges that cross both the subarrays, we need to find the number of pairs of indices i and j such that i < j and prefixSum[j] - prefixSum[i] falls within the range of [low, high] but j is in the right subarray and i is in the left subarray.

To find these cross ranges, we can use two pointer method. We have to find two pointers i and j such that i is in the left subarray and j is in the right subarray. The difference between the prefix sums at i and j (prefixSum[j] - prefixSum[i]) will give us the sum of the subarray from i to j. If this sum falls within the range of [low, high], We can count this cross range.

Step 4: Merging

The final step is to merge the two subarrays and return the total count of the number of ranges.

Here is the Python code that implements the above solution:

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        
        def countRangeSumRecursive(nums: List[int], lower: int, upper: int, left: int, right: int) -> int:
            if left == right:
                return 0
            
            mid = (left + right) // 2
            count = countRangeSumRecursive(nums, lower, upper, left, mid) + countRangeSumRecursive(nums, lower, upper, mid + 1, right)
            
            i = left
            j = k = mid + 1
            
            while i <= mid:
                while j <= right and prefixSum[j] - prefixSum[i] < lower: j += 1
                while k <= right and prefixSum[k] - prefixSum[i] <= upper: k += 1
                count += k - j
                i += 1
            
            sortedPrefixSum = [0] * (right - left + 1)
            i = left
            j = mid + 1
            k = 0
            
            while k < len(sortedPrefixSum):
                if i <= mid and (j > right or prefixSum[i] <= prefixSum[j]):
                    sortedPrefixSum[k] = prefixSum[i]
                    i += 1
                else:
                    sortedPrefixSum[k] = prefixSum[j]
                    j += 1
                k += 1
            
            prefixSum[left:right + 1] = sortedPrefixSum
            
            return count
        
        prefixSum = [0] * (len(nums) + 1)
        
        for i in range(len(nums)):
            prefixSum[i + 1] = prefixSum[i] + nums[i]
            
        return countRangeSumRecursive(nums, lower, upper, 0, len(nums))

In this code, we first create the prefixSum array. Then we use the countRangeSumRecursive function to recursively count the number of ranges within each subarray. We use the two-pointer method to count the number of cross ranges, and then merge the subarrays to get the final count.

Overall, this is a complex problem that requires a bit of thought to get the solution right. However, with careful implementation, we can solve this problem efficiently.

1