HardArrayMerge SortDivide and ConquerBinary Indexed Tree

Count of Range Sum

1 approach, code in every language

Given an integer array along with an inclusive lower and upper bound, count how many contiguous slices have a sum that lands inside the bound. Equivalently, count index pairs i ≤ j whose slice total falls between lower and upper, both inclusive.

Building a prefix-sum array turns each slice total into the difference of two prefix sums. Counting pairs of prefix sums whose difference stays inside the bound can then be folded into a merge sort, which counts qualifying pairs while it merges sorted halves.

Example 1

Input: nums = [-2,5,-1], lower = -2, upper = 2

Output: 3

The slices that total within [-2, 2] are [-2] (sum -2), [-1] (sum -1), and [-2,5,-1] (sum 2).

Example 2

Input: nums = [0], lower = 0, upper = 0

Output: 1

The single slice [0] sums to 0, which lies in the range.

Constraints

1 ≤ nums.length ≤ 10^5
-2^31 ≤ nums[i] ≤ 2^31 - 1
-10^5 ≤ lower ≤ upper ≤ 10^5

Prefix Sums + Merge Sort Counting

Form prefix sums, then run a merge sort where, before merging two sorted halves, count the right-half prefix sums whose gap from each left-half prefix sum stays inside the bounds.

Loading animation…

Intuition

A slice sum equals prefix[j] - prefix[i] with i < j, so the task is counting prefix-sum pairs whose difference sits in the range. During merge sort both halves become sorted, and for a fixed left prefix value the qualifying right values form a contiguous window. Because the left half is sorted, that window's boundaries only slide forward as the left value grows, so two moving pointers count matches for the whole left half in linear time per merge. Summing these counts across every merge level yields the total. Prefix sums must use 64-bit integers to avoid overflow.

Algorithm walkthrough

1Build a prefix-sum array of length n+1 using 64-bit integers, with prefix[0] = 0.
2Recursively merge sort the prefix array; the answer accumulates across recursive calls.
3Before merging a left and right half, for each left value advance two pointers over the right half to find how many right values satisfy lower ≤ right - left ≤ upper, adding that window width to the count.
4Merge the two sorted halves back together so the parent call sees a sorted range.
5Return the total count produced by the top-level call.

Implementation

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        prefix = [0] * (len(nums) + 1)
        for i, v in enumerate(nums):
            prefix[i + 1] = prefix[i] + v

        def merge_sort(lo: int, hi: int) -> int:
            if hi - lo <= 1:
                return 0
            mid = (lo + hi) // 2
            count = merge_sort(lo, mid) + merge_sort(mid, hi)
            j = k = mid
            for left_val in prefix[lo:mid]:
                while j < hi and prefix[j] - left_val < lower:
                    j += 1
                while k < hi and prefix[k] - left_val <= upper:
                    k += 1
                count += k - j
            prefix[lo:hi] = sorted(prefix[lo:hi])
            return count

        return merge_sort(0, len(prefix))

Time

O(n log n)

Space

O(n)

Prefix array plus a merge buffer, both size n+1.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reservoir Swing Bands is our own problem on the technique behind Count of Range Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free