LeetCode Solutions Blog

Count of Range Sum

Number: 327

Difficulty: Hard

Paid? No

Problem Description

Given an integer array nums and two integers lower and upper, count the number of range sums S(i, j) (the sum of elements from index i to j inclusive, where i ≤ j) that lie within the inclusive range [lower, upper].

Key Insights

Transform the problem using prefix sums. Define prefix[i] as the sum of elements nums[0] to nums[i-1] which simplifies S(i, j) to prefix[j+1] - prefix[i].
The problem then reduces to counting, for every prefix[j+1], how many earlier prefix[i] satisfy: lower ≤ prefix[j+1] - prefix[i] ≤ upper.
Use a modified merge sort (or other data structures like Binary Indexed Tree or Segment Tree) to count the number of valid pairs while sorting the prefix sum array.
The merge step cleverly counts the number of valid prefix differences before merging two sorted halves.

Space and Time Complexity

Time Complexity: O(n log n) due to merge sort style divide and conquer. Space Complexity: O(n) for the prefix sum and temporary arrays used in merging.

Solution

We transform the input array nums into a prefix sum array. For each new prefix sum, we search the sorted list of previous prefix sums to count how many fall into the range [current - upper, current - lower]. This is efficiently done during the merge sort process where each merge step counts the valid pairs between the two sorted subarrays. The merge sort guarantees that the array segments are sorted, which allows binary-counting of valid ranges by maintaining two pointers. This approach eliminates the need for nested loops and achieves O(n log n) complexity.

Code Solutions

# Python implementation using merge sort style divide and conquer

def countRangeSum(nums, lower, upper):
    # Build prefix sum array - prefix[i] is the sum of nums[0] up to nums[i-1].
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    
    # Helper function to count valid range sums during merge sort.
    def merge_sort(start, end):
        if end - start <= 1:  # Base case: one element is already sorted.
            return 0
        mid = (start + end) // 2
        count = merge_sort(start, mid) + merge_sort(mid, end)
        # Two pointers for the merging process
        j = k = mid
        temp = []
        r = mid
        # Iterate over the left part
        for left in prefix[start:mid]:
            # Increase k while the condition is not satisfied.
            while k < end and prefix[k] - left < lower:
                k += 1
            # Increase j while the condition is met.
            while j < end and prefix[j] - left <= upper:
                j += 1
            count += j - k

        # Standard merge sort merge operation.
        l, r = start, mid
        sorted_list = []
        while l < mid and r < end:
            if prefix[l] <= prefix[r]:
                sorted_list.append(prefix[l])
                l += 1
            else:
                sorted_list.append(prefix[r])
                r += 1
        # Append remaining elements.
        sorted_list.extend(prefix[l:mid])
        sorted_list.extend(prefix[r:end])
        # Write back sorted list into prefix.
        prefix[start:end] = sorted_list
        return count

    return merge_sort(0, len(prefix))

# Example usage:
print(countRangeSum([-2,5,-1], -2, 2))  # Output: 3