Abstract / Summary

Count how many subarray sums fall within a given range using efficient methods without brute force.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 39% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Indexed Tree
• Binary Search
• Divide And Conquer
• Merge Sort
• Ordered Set
• Segment Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “count of range sum” problem by converting the original array into a sequence of prefix sums, deduplicating and sorting those sums, and then using binary search together with a frequency vector to accumulate the answer. The algorithm proceeds in two distinct phases: preparation of the unique sorted prefix sums and a single pass that updates a running total while querying the frequency vector for valid previous sums.

Key Steps

The first phase builds the prefix-sum array and extracts the distinct values.

vector<int64_t> sums;
int64_t sum = 0;
for (auto n : nums)
{
    sum += n;
    sums.push_back(sum);
}
sort(sums.begin(), sums.end());
auto last = unique(sums.begin(), sums.end());
sums.resize(distance(sums.begin(), last));

Here each element of nums contributes to a cumulative total stored in sum. The vector sums therefore holds all prefix sums in the order they appear. Sorting followed by unique removes duplicates, guaranteeing that later binary searches operate on a strictly increasing sequence.

The second phase iterates through the original array again, maintaining a running prefix sum and a parallel frequency vector count that records how many times each unique prefix sum has been seen so far.

sum = 0;
vector<int> count(sums.size(), 0);
for (auto n : nums)
{
    sum += n;

    if (sum >= lower && sum <= upper)
        result++;

    auto a = distance(sums.begin(), lower_bound(sums.begin(), sums.end(), sum - upper));
    auto b = distance(sums.begin(), upper_bound(sums.begin(), sums.end(), sum - lower));
    for (; a != b; a++)
        result += count[a];

    auto current = distance(sums.begin(), lower_bound(sums.begin(), sums.end(), sum));
    count[current]++;
}

The conditional if (sum >= lower && sum <= upper) captures subarrays that start at index 0. The interval [sum-upper, sum-lower] represents all earlier prefix sums that, when subtracted from the current sum, produce a range sum within [lower, upper]. The lower_bound and upper_bound calls locate the first and one-past-last positions of that interval in the sorted sums. A simple loop iterates over the indices between a and b, adding the stored frequencies from count to result. Finally, the current prefix sum’s index is found with another lower_bound, and its frequency is incremented.

Edge Cases Handled

When the input vector nums is empty, the initial loop that builds sums does not execute, leaving sums empty. The subsequent sort and unique operations are safe on an empty container, and the second pass also skips entirely, resulting in a return value of 0, which correctly reflects that no subarray exists.

If all elements of nums are zero, every prefix sum is zero. The deduplication step collapses the entire sums vector to a single entry, and the frequency vector count has size 1. The binary-search bounds for sum-upper and sum-lower both resolve to the same index, and the inner loop correctly aggregates the count of previous zero sums, handling the large number of overlapping subarrays without overflow.

When lower equals upper, the interval [sum-upper, sum-lower] collapses to a single value. The use of lower_bound for the left edge and upper_bound for the right edge ensures that the loop iterates over exactly those prefix sums equal to sum-lower, correctly counting subarrays whose sum matches the exact target.

The code stores prefix sums in a 64-bit integer (int64_t). This prevents overflow for inputs where the cumulative sum exceeds the range of a 32-bit integer, especially when nums contains large positive or negative values.

Performance Optimizations

The algorithm deliberately avoids a map-based solution, which would incur logarithmic updates for each element. By extracting all unique prefix sums once, sorting them, and then using binary search on a contiguous vector, the code benefits from cache-friendly memory access patterns and the low overhead of std::vector.

The frequency vector count replaces a hash table or balanced tree for tracking occurrences of each prefix sum. Since the index of a prefix sum is known after the binary search, incrementing the corresponding entry in count is an O(1) operation, and the subsequent look-ups for the range [sum-upper, sum-lower] are reduced to a simple loop over a contiguous slice of the vector.

Using distance together with lower_bound/upper_bound yields integer indices directly, avoiding the need for iterator arithmetic later in the loop. This small detail eliminates extra indirection when accessing count.

Finally, the early check if (sum >= lower && sum <= upper) captures the case where a subarray starts at the first element without invoking the binary-search machinery, saving work for the common scenario where many prefix sums fall inside the target interval.

Imagine having a long line of blocks, each with a different number painted on it. This program is like a clever helper trying to find every possible group of blocks sitting next to each other where the total sum of their numbers is just right. The helper wants the total to stay between two specific goals, which are called lower and upper.

To start, the helper pretends to walk down the line of blocks from the very beginning. As it walks, it keeps a running count of all the numbers it has seen so far. It writes down every one of these running totals into a special list. Once it has all those totals, it sorts them from smallest to largest and removes any duplicates so that it has a clean and organized map of where every sum sits.

Now that the helper has a map, it goes through the line of blocks one more time. This time, it looks at the running total again and checks if that total happens to land right between the two goals. After that, it uses the map it made earlier to look backward at the previous running totals. It performs a little search to see which of those past sums, when taken away from the current total, leaves a result that fits perfectly within the bounds. Every time it finds a group that matches the goal, it adds one to its final score. As it finishes checking each block, it updates its count of past totals so everything stays perfectly updated for the next step of the journey.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++				Python		Java			TS
	WalkCCC	C++				Python		Java
	leetcode.ca	C++				Python		Java	Go		TS
	LeetcodeHelp	C++				Python		Java
	MemoryLimitExceeded	C++				Python
	Progiez	C++				Python		Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai							Java
	everthis		JS
	halfrost								Go
	haoel	C++
	JoshCrozier		JS
	linouk23	C++
	lkwq007					Python
	MacJim	C++
	ruoru				Rust
	suxrobGM			C#
	vli02									C
	wisdompeak	C++
	yuanliu666						Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
vli02	C
wisdompeak	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality