Count of Range Sum

1. Define the problem

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] , inclusive. A range sum nums[i..j] is exactly prefix[j+1] - prefix_i for a padded prefix array. Build that prefix array once, then check every pair of prefix values for a difference inside the target range.

Constraints

1 ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums_i ≤ 2³¹ - 1
-10⁵ ≤ lower ≤ upper ≤ 10⁵

Example

Inputnums = [-2, 5, -1], lower = -2, upper = 2

Output3

Explanation Three range sums fall in [-2, 2]: nums[0..0] = -2, nums[2..2] = -1, and nums[0..2] = 2.

2. Know the words first

In plain terms

Range sum: The sum of a contiguous slice of the array, nums_i + nums[i+1] + ... + nums_j, written as nums[i..j].

3. Visualize the solution

Build the prefix array, then test every pair of prefix values

p00

p1—

p2—

p3—

Statusbuild · count: 0

Start the prefix array with p0 = 0 — the sum of nothing. The other cells are still empty.

What happens in this step

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

prefix[0] = 0

The padded first cell stands for "no elements taken yet". It is what
lets a slice that starts at index 0 be written as a difference of two
prefix values, just like every other slice.

Step 1 of 5

Steps to visualize

The row is the padded prefix array for nums = [-2, 5, -1]. p0 is 0, and p[i+1] = p_i + nums_i. Cells fill in as the array is built; — means not computed yet.
Once the row is full, the sum of any slice of nums is the difference between two of its cells: prefix_j - prefix_i.
Walk every pair i < j and count it whenever that difference falls inside [lower, upper]. The frame shows the pair being tested.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Build the prefix array, then test every pair of prefix values

p00

p1—

p2—

p3—

Statusbuild · count: 0

Start the prefix array with p0 = 0 — the sum of nothing. The other cells are still empty.

What happens in this step

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

prefix[0] = 0

The padded first cell stands for "no elements taken yet". It is what
lets a slice that starts at index 0 be written as a difference of two
prefix values, just like every other slice.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function countRangeSum(nums, lower, upper) {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }

  let count = 0;
  for (let i = 0; i < prefix.length; i++) {
    for (let j = i + 1; j < prefix.length; j++) {
      const rangeSum = prefix[j] - prefix[i];
      if (rangeSum >= lower && rangeSum <= upper) {
        count++;
      }
    }
  }

  return count;
}

Time: O(n^2), improvable to O(n log n) with a merge-sort count
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [-2, 5, -1], lower = -2, upper = 2`	`3`	example from the docstring
`nums = [0], lower = 0, upper = 0`	`1`	smallest valid input, a single value inside the range
`nums = [5], lower = 0, upper = 2`	`0`	a single value outside the range
`nums = [1, 1, 1], lower = 0, upper = 5`	`6`	a wide range where every possible subarray sum counts
`nums = [1, -1, 1, -1], lower = 0, upper = 0`	`4`	negative values producing several zero-sum ranges
`nums = [2, 2, 2], lower = -100, upper = 100`	`6`	a range wide enough to include every subarray sum

Count of Range Sum