#327

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Count of Range Sum

Count the number of subarray sums within a given inclusive range using optimized divide-and-conquer techniques efficiently.

array binary search divide and conquer binary indexed tree segment tree

Problem Statement

Given an integer array nums and two integers lower and upper, determine the total number of subarrays whose sums lie between lower and upper, inclusive. A subarray is defined as a contiguous segment of nums, and sums can be negative or positive.

Formally, for indices i and j with 0 <= i <= j < nums.length, compute the sum S(i, j) = nums[i] + nums[i+1] + ... + nums[j], and count how many such sums satisfy lower <= S(i, j) <= upper. For example, nums = [-2,5,-1], lower = -2, upper = 2 produces 3 valid ranges: [0,0], [2,2], and [0,2].

Examples

Example 1

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

Output: 3

The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2

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

Output: 1

Example details omitted.

Constraints

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
The answer is guaranteed to fit in a 32-bit integer.

Solution Approach

Prefix Sum with Merge Sort

Compute prefix sums of nums and recursively divide the array. During merge steps, count valid sums where the difference between two prefix sums falls within [lower, upper]. This approach reduces time complexity compared to naive O(n^2) enumeration and handles overlapping ranges efficiently.

Segment Tree or Binary Indexed Tree

Map prefix sums into a sorted structure, then query ranges efficiently using a segment tree or BIT. For each new prefix sum, count how many previous sums satisfy the range condition. This approach works well when dynamic updates or multiple queries are needed.

Binary Search over Valid Sum Space

Sort all prefix sums and for each prefix sum, use binary search to find how many previous sums lie in [currentSum - upper, currentSum - lower]. This directly applies the 'binary search over the valid answer space' pattern and ensures logarithmic counting per prefix sum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Naive enumeration is O(n^2). Merge sort-based prefix sum counting achieves O(n log n). Segment tree or BIT approaches also achieve O(n log n) with extra space for the data structure. Space is O(n) for prefix sums, and extra O(n) for merge operations or tree structures.

What Interviewers Usually Probe

Ask about handling negative numbers in subarray sums.
Probe understanding of prefix sums and why merge sort helps avoid double counting.
Expect recognition of binary search over cumulative sums as the core optimization.

Common Pitfalls or Variants

Common pitfalls

Attempting brute-force O(n^2) sum enumeration on large arrays causes timeouts.
Neglecting proper handling of overlapping ranges during merge can undercount valid sums.
Failing to correctly compute prefix sum differences when applying binary search leads to off-by-one errors.

Follow-up variants

Count of Range Sum where multiple queries on different ranges are performed, requiring dynamic updates.
Counting subarrays with product in a range instead of sum, which changes the aggregation technique.
Counting ranges with additional constraints, like length limits or modulo conditions.

FAQ

What is the main pattern used in Count of Range Sum?

The key pattern is 'binary search over the valid answer space', combined with prefix sums and merge sort to count subarrays efficiently.

Can this problem be solved without merge sort?

Yes, segment trees or binary indexed trees can be used to query prefix sum ranges dynamically, still achieving O(n log n) complexity.

Why is prefix sum necessary here?

Prefix sums allow computing any subarray sum as a simple difference, reducing the problem from O(n^2) enumeration to a more efficient approach.

What common mistakes cause incorrect counts?

Off-by-one errors, failing to include negative sums, and mismanaging overlapping ranges during merge or binary search are frequent pitfalls.

What constraints affect solution choice?

Large array sizes up to 10^5 and sum ranges up to ±10^5 require O(n log n) methods; naive O(n^2) approaches are infeasible.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x, v):
        while x <= self.n:
            self.c[x] += v
            x += x & -x

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        s = list(accumulate(nums, initial=0))
        arr = sorted(set(v for x in s for v in (x, x - lower, x - upper)))
        tree = BinaryIndexedTree(len(arr))
        ans = 0
        for x in s:
            l = bisect_left(arr, x - upper) + 1
            r = bisect_left(arr, x - lower) + 1
            ans += tree.query(r) - tree.query(l - 1)
            tree.update(bisect_left(arr, x) + 1, 1)
        return ans

Continue Practicing

#315 count of smaller numbers after self #493 reverse pairs #1649 create sorted array through instructions