DSA problem
Count of Range Sum
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 S(i, j) is defined as the sum of elements in nums between indices i and j (i <= j), inclusive.
The naive O(n²) approach enumerates every (i, j) pair and checks whether S(i, j) lies in the target interval. With n up to 10⁵, that is far too slow. The key reformulation is to use prefix sums: define P[0] = 0 and P[k] = nums[0] + nums[1] + ... + nums[k-1]. Then S(i, j) = P[j + 1] - P[i], so we need to count pairs (a, b) with a < b and lower <= P[b] - P[a] <= upper.
This counting-pairs-by-difference problem on an array of prefix sums is a classic application of modified merge sort. During merge sort on the prefix sums, at every merge step both halves are sorted; for each prefix P[a] in the left half we can find, with a sliding two-pointer sweep, the range of indices b in the right half such that lower <= P[b] - P[a] <= upper. Because both halves are sorted, these pointers only move forward, giving a total-linear count per merge level.
After counting cross-half pairs, perform the standard linear merge to keep the halves combined as a sorted run for the next level up. Because prefix sums of values up to 2³¹ - 1 over up to 10⁵ elements can exceed 32-bit range, we store P as 64-bit integers (long / long long); JavaScript's native Number is also safe within 53 bits given the constraints. Final complexity: O(n log n) time and O(n) extra space.
Examples
nums = [-2,5,-1], lower = -2, upper = 23nums = [0], lower = 0, upper = 01nums = [-3,1,2,-2,2,-1], lower = -3, upper = -17Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- -10^5 <= lower <= upper <= 10^5
- Prefix sums can exceed 32-bit range — use a 64-bit type (long / long long).
- The answer is guaranteed to fit into a 32-bit signed integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.