We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count of Range Sum

Difficulty: Hard

Problem Description

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Key Insights

  • The problem requires counting the number of contiguous subarrays whose sum falls within a specified range.
  • A prefix sum approach can be utilized to efficiently calculate the sum of any subarray.
  • Utilizing a modified merge sort or a balanced binary search structure can help maintain the counts of prefix sums and facilitate range queries.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve this problem, we can use the prefix sum technique combined with a modified merge sort. First, we compute the prefix sums for the array, which allows us to calculate the sum of any subarray in constant time. The main idea is to count how many prefix sums fall within the range [current_sum - upper, current_sum - lower] using a sorted list of previously seen prefix sums. We can efficiently keep this list sorted and perform binary search to count the valid ranges. This approach not only keeps track of the prefix sums but also counts how many of them lie within the given bounds.

Code Solutions

def countRangeSum(nums, lower, upper):
    prefix_sums = [0]
    for num in nums:
        prefix_sums.append(prefix_sums[-1] + num)

    def merge_count(start, mid, end):
        count = 0
        j = k = mid + 1
        for i in range(start, mid + 1):
            while j <= end and prefix_sums[j] - prefix_sums[i] < lower:
                j += 1
            while k <= end and prefix_sums[k] - prefix_sums[i] <= upper:
                k += 1
            count += k - j
        # Merge step
        prefix_sums[start:end + 1] = sorted(prefix_sums[start:end + 1])
        return count

    def merge_sort(start, end):
        if start >= end:
            return 0
        mid = (start + end) // 2
        count = merge_sort(start, mid) + merge_sort(mid + 1, end)
        count += merge_count(start, mid, end)
        return count

    return merge_sort(0, len(prefix_sums) - 1)
← Back to All Questions