Introduction

Given an array and a range [low, high], the task is to find all contiguous subarrays whose sums lie in that range. The important nuance is the word all. That changes the complexity discussion completely. If the output itself can contain quadratic-many subarrays, then no algorithm can list them all in truly subquadratic time in the worst case.

Why Output Size Matters

Suppose the array is all zeros and the range is [0, 0]. Every contiguous subarray qualifies.

For an array of length n, the number of contiguous subarrays is:

n * (n + 1) / 2

That is O(n^2). So if you must enumerate all matching subarrays, the worst-case output size is already quadratic.

That means:

• enumerating all answers cannot beat O(n^2) worst-case output time
• counting the number of answers might be improved
• deciding whether at least one answer exists might be improved further

Interview solutions often miss this distinction.

The Baseline With Prefix Sums

A straightforward improvement over recomputing sums from scratch is to use prefix sums.

If prefix[i] is the sum of the first i elements, then the sum of subarray i..j is:

prefix[j + 1] - prefix[i]

That reduces each subarray-sum query to O(1) after O(n) preprocessing.

1def all_subarrays_in_range(nums, low, high):
2    prefix = [0]
3    for value in nums:
4        prefix.append(prefix[-1] + value)
5
6    result = []
7    for start in range(len(nums)):
8        for end in range(start, len(nums)):
9            total = prefix[end + 1] - prefix[start]
10            if low <= total <= high:
11                result.append((start, end, total))
12    return result
13
14
15print(all_subarrays_in_range([1, 2, -1, 3], 2, 4))

This is still O(n^2) time for enumeration, but it is the correct clean baseline.

Can We Do Better Than O(n^2)

If the requirement is to list every valid subarray, not in the worst case. The output lower bound blocks that.

If the requirement is only to count valid subarrays, then yes, you can do better than checking all pairs explicitly. The prefix-sum problem becomes a range-counting problem:

For each ending position j, count earlier prefix sums p such that:

low <= prefix[j] - p <= high

Rearranging:

prefix[j] - high <= p <= prefix[j] - low

Now the task is to count how many previous prefix sums fall in a numeric interval.

Better Counting With Ordered Structures

To count instead of enumerate, you can maintain prior prefix sums in an ordered data structure and perform range-count queries.

Possible tools include:

• balanced binary search trees with augmented counts
• Fenwick trees after coordinate compression
• merge-sort based divide-and-conquer, similar to count-of-range-sum problems

That brings the counting complexity down to roughly O(n log n).

A merge-sort style counter in Python looks like this:

1def count_range_sums(nums, low, high):
2    prefix = [0]
3    for x in nums:
4        prefix.append(prefix[-1] + x)
5
6    def sort_count(arr):
7        if len(arr) <= 1:
8            return arr, 0
9
10        mid = len(arr) // 2
11        left, count_left = sort_count(arr[:mid])
12        right, count_right = sort_count(arr[mid:])
13
14        count = count_left + count_right
15        j = k = 0
16
17        for value in left:
18            while k < len(right) and right[k] - value < low:
19                k += 1
20            while j < len(right) and right[j] - value <= high:
21                j += 1
22            count += j - k
23
24        merged = []
25        i = r = 0
26        while i < len(left) and r < len(right):
27            if left[i] <= right[r]:
28                merged.append(left[i])
29                i += 1
30            else:
31                merged.append(right[r])
32                r += 1
33        merged.extend(left[i:])
34        merged.extend(right[r:])
35        return merged, count
36
37    return sort_count(prefix)[1]
38
39
40print(count_range_sums([1, 2, -1, 3], 2, 4))

This counts matches efficiently, but it does not list all matching index pairs.

Special Case: All Numbers Non-Negative

If all array values are non-negative, sliding-window techniques become more useful because subarray sums grow monotonically as the right boundary moves. But once negative values are allowed, that monotonicity disappears and simple two-pointer strategies stop working for the general case.

Because the interview title says integers, you should assume negatives are possible unless the interviewer narrows the problem.

What a Strong Interview Answer Sounds Like

A strong answer is:

1. naive enumeration is O(n^3) if you sum each subarray directly
2. prefix sums reduce that to O(n^2) for enumeration
3. worst-case listing of all results cannot beat O(n^2) because the output may itself be quadratic
4. if the task changes to counting, there are O(n log n) approaches

That is the right tradeoff discussion.

Common Pitfalls

The biggest pitfall is claiming an O(n log n) algorithm for enumerating all valid subarrays without acknowledging the output-size lower bound.

Another issue is using a sliding window when negative numbers are allowed. That only works under stronger assumptions.

Be careful to separate three different tasks: existence, counting, and enumeration. They do not have the same optimal complexity.

Finally, prefix sums speed up sum computation, but they do not magically remove the quadratic number of start and end pairs when you must list them.

Summary

• If you must list all qualifying contiguous subarrays, worst-case O(n^2) time is unavoidable.
• Prefix sums reduce naive enumeration to a clean O(n^2) solution.
• The reason you cannot do better in general is that the output itself can be quadratic.
• If you only need the count, O(n log n) solutions exist.
• Sliding-window methods do not solve the general integer case when negative values are allowed.
• In interviews, distinguish clearly between enumerating, counting, and detecting existence.