Count of Range Sum solution and explanation
Google
9 more videos on this problem
LeetCode 327. Count of Range Sum Explanation and Solutionhappygirlzt · 21:05 · 20K views
327. Count of Range Sum (Leetcode Hard)Programming Live with Larry · 47:40 · 8K views
Leetcode Question 327 "Count of Range Sum" in JavaGhumman Tech · 13:27 · 4K views
LeetCode 327. Count of Range Sum 中文解释 Chinese Versionhappygirlzt · 20:58 · 3K views
94. Leetcode 327. Count of Range Sum : JavascriptWeb Fusion with Bharadwaj · 45:59 · 1K views
P5. Count of Range Sum || Ordered Set || C++ || GET CONCEPTGET CONCEPT · 37:36 · 1K views
Leetcode 327 Count of Range Sum | 前缀和 归并排序大叔与小白 · 13:30 · 248 views
Count Of Range SumOwen Wu · 13:04 · 217 views
Leetcode 0327. Count of Range SumFearless Learner · 11:43 · 212 views
No Sound Leetcode 327: Count of Range SumExtremeProgrammer · 2:36 · 147 views
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.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
Example 1:
Input: nums = [-2,5,-1], lower = -2, upper = 2 Output: 3 Explanation: 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
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.
Approach overview
Problem Overview: Given an integer array nums and two integers lower and upper, count the number of subarrays whose sum lies within the inclusive range [lower, upper]. The challenge is efficiently evaluating all possible subarray sums without explicitly enumerating every pair.
The key observation is that subarray sums can be rewritten using prefix sums. If prefix[i] represents the sum of the first i elements, then the sum of subarray (i, j] equals prefix[j] - prefix[i]. The problem becomes: for every j, count how many earlier prefix values satisfy lower ≤ prefix[j] - prefix[i] ≤ upper.
Approach 1: Naive Iteration with Prefix Sums (Time: O(n²), Space: O(n))
Start by building a prefix sum array so each subarray sum can be computed in constant time. Iterate over every possible pair of indices (i, j) where i < j, compute the subarray sum using prefix[j] - prefix[i], and check if it falls within the target range. This avoids recomputing sums repeatedly but still examines all O(n²) subarrays.
This method is easy to implement and useful for validating correctness during development. However, it becomes too slow when the input size approaches the typical constraints (up to tens of thousands of elements). The approach mainly demonstrates the relationship between subarray sums and prefix differences in an array.
Approach 2: Merge Sort with Prefix Sums (Time: O(n log n), Space: O(n))
The optimized solution uses a modified divide and conquer strategy similar to counting inversions. Compute the prefix sum array first. While performing a merge sort on this array, count valid pairs across the left and right halves.
For each prefix value in the left half, maintain two pointers in the right half that represent the valid window where lower ≤ rightPrefix - leftPrefix ≤ upper. Because both halves are sorted during the merge step, these pointers only move forward, allowing the algorithm to count valid ranges in linear time per merge level. After counting, perform the normal merge to keep the prefix array sorted.
This reduces the overall complexity to O(n log n), making it scalable for large inputs. The algorithm relies on sorting properties and efficient window counting instead of explicitly enumerating subarrays.
Recommended for interviews: Interviewers typically expect the merge-sort-based prefix sum approach. The brute force solution shows you understand the prefix sum transformation, but the O(n log n) divide-and-conquer strategy demonstrates stronger algorithmic thinking and familiarity with advanced counting techniques.
Approach 1: Approach 1: Naive Iteration
This approach involves using two nested loops to calculate the range sum for each subarray and checks if it lies between the given range [lower, upper]. The approach is straightforward but results in O(n^2) time complexity, making it inefficient for large input sizes.
def countRangeSum(nums, lower, upper):
count = 0
for i in range(len(nums)):
total = 0
for j in range(i, len(nums)):
total += nums[j]
if lower <= total <= upper:
count += 1
return count
nums = [-2, 5, -1]
lower = -2
upper = 2
print(countRangeSum(nums, lower, upper))public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
long sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {-2, 5, -1};
int lower = -2, upper = 2;
System.out.println(sol.countRangeSum(nums, lower, upper));
}
}#include <vector>
using namespace std;
int countRangeSum(vector<int>& nums, int lower, int upper) {
int count = 0;
for (size_t i = 0; i < nums.size(); i++) {
long sum = 0;
for (size_t j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {-2, 5, -1};
int lower = -2, upper = 2;
printf("%d\n", countRangeSum(nums, lower, upper));
return 0;
}function countRangeSum(nums, lower, upper) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
let nums = [-2, 5, -1];
let lower = -2;
let upper = 2;
console.log(countRangeSum(nums, lower, upper));#include <stdio.h>
int countRangeSum(int* nums, int numsSize, int lower, int upper) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
long sum = 0;
for (int j = i; j < numsSize; j++) {
sum += nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {-2, 5, -1};
int lower = -2, upper = 2;
printf("%d\n", countRangeSum(nums, 3, lower, upper));
return 0;
}using System;
public class Solution {
public int CountRangeSum(int[] nums, int lower, int upper) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
long sum = 0;
for (int j = i; j < nums.Length; j++) {
sum += nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {-2, 5, -1};
int lower = -2, upper = 2;
Console.WriteLine(sol.CountRangeSum(nums, lower, upper));
}
}This Python implementation uses two loops to examine each subarray, summing from a starting index specified by the outer loop, and extending the subarray using the inner loop.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Approach 2: Merge Sort with Prefix Sums
This approach utilizes merge sort combined with prefix sums to efficiently calculate and count the number of range sums within the given boundaries. The key insight is that any valid range must be a difference between two prefix sums. By maintaining and sorting prefix sums, the problem is reduced to counting the number of such prefix sums differences that fall within the range, which can be done in logarithmic time using the divide and conquer method of merge sort.
def countRangeSum(nums, lower, upper):
def sort_and_count(sums, start, end, lower, upper):
if end - start <= 1:
return 0
mid = (start + end) // 2
count = sort_and_count(sums, start, mid, lower, upper) + \
sort_and_count(sums, mid, end, lower, upper)
j = k = t = mid
cache = []
for left in sums[start:mid]:
while j < end and sums[j] - left < lower:
j += 1
while k < end and sums[k] - left <= upper:
k += 1
while t < end and sums[t] < left:
cache.append(sums[t])
t += 1
cache.append(left)
count += k - j
sums[start:start + len(cache)] = cache
return count
sums = [0]
for num in nums:
sums.append(sums[-1] + num)
return sort_and_count(sums, 0, len(sums), lower, upper)
nums = [-2, 5, -1]
lower = -2
upper = 2
print(countRangeSum(nums, lower, upper))public class Solution {
private void sortAndCount(long[] sums, int start, int end, int lower, int upper, int[] count) {
if (end - start <= 1) return;
int mid = start + (end - start) / 2;
sortAndCount(sums, start, mid, lower, upper, count);
sortAndCount(sums, mid, end, lower, upper, count);
int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
for (int i = start, r = 0; i < mid; ++i, ++r) {
while (j < end && sums[j] - sums[i] < lower) j++;
while (k < end && sums[k] - sums[i] <= upper) k++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
count[0] += k - j;
}
System.arraycopy(cache, 0, sums, start, t - start);
}
public int countRangeSum(int[] nums, int lower, int upper) {
long[] sums = new long[nums.length + 1];
sums[0] = 0;
for (int i = 0; i < nums.length; i++) {
sums[i + 1] = sums[i] + nums[i];
}
int[] count = {0};
sortAndCount(sums, 0, sums.length, lower, upper, count);
return count[0];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {-2, 5, -1};
int lower = -2, upper = 2;
System.out.println(sol.countRangeSum(nums, lower, upper));
}
}#include <vector>
#include <algorithm>
using namespace std;
void mergeAndCount(vector<long>& sums, int start, int mid, int end, int lower, int upper, int& count) {
int j = mid, k = mid, t = mid;
vector<long> cache(end - start);
int r = 0;
for (int i = start; i < mid; ++i) {
while (j < end && sums[j] - sums[i] < lower) j++;
while (k < end && sums[k] - sums[i] <= upper) k++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r++] = sums[i];
count += k - j;
}
move(cache.begin(), cache.begin() + (t - start), sums.begin() + start);
}
void sortAndCount(vector<long>& sums, int start, int end, int lower, int upper, int& count) {
if (end - start <= 1) return;
int mid = start + (end - start) / 2;
sortAndCount(sums, start, mid, lower, upper, count);
sortAndCount(sums, mid, end, lower, upper, count);
mergeAndCount(sums, start, mid, end, lower, upper, count);
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
vector<long> sums(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); ++i) {
sums[i + 1] = sums[i] + nums[i];
}
int count = 0;
sortAndCount(sums, 0, sums.size(), lower, upper, count);
return count;
}
int main() {
vector<int> nums = {-2, 5, -1};
int lower = -2, upper = 2;
printf("%d\n", countRangeSum(nums, lower, upper));
return 0;
}function countRangeSum(nums, lower, upper) {
function sortAndCount(sums, start, end, lower, upper) {
if (end - start <= 1) return 0;
const mid = Math.floor((start + end) / 2);
let count = sortAndCount(sums, start, mid, lower, upper) +
sortAndCount(sums, mid, end, lower, upper);
let j = mid, k = mid, t = mid;
const cache = [];
for (let i = start, r = 0; i < mid; ++i) {
while (j < end && sums[j] - sums[i] < lower) j++;
while (k < end && sums[k] - sums[i] <= upper) k++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r++] = sums[i];
count += k - j;
}
for (let i = 0; i < t - start; ++i) {
sums[start + i] = cache[i];
}
return count;
}
const sums = [0];
for (const num of nums) {
sums.push(sums[sums.length - 1] + num);
}
return sortAndCount(sums, 0, sums.length, lower, upper);
}
let nums = [-2, 5, -1];
let lower = -2, upper = 2;
console.log(countRangeSum(nums, lower, upper));#include <stdio.h>
#include <stdlib.h>
void mergeAndCount(long sums[], int start, int mid, int end, int lower, int upper, int* count) {
int j = mid, k = mid, t = mid;
int len = end - start;
long* cache = (long*)malloc(len * sizeof(long));
for (int i = start, r = 0; i < mid; ++i, ++r) {
while (j < end && sums[j] - sums[i] < lower) j++;
while (k < end && sums[k] - sums[i] <= upper) k++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
*count += k - j;
}
for (int i = start; i < t; ++i) {
sums[i] = cache[i - start];
}
free(cache);
}
void sortAndCount(long sums[], int start, int end, int lower, int upper, int* count) {
if (end - start <= 1) return;
int mid = start + (end - start) / 2;
sortAndCount(sums, start, mid, lower, upper, count);
sortAndCount(sums, mid, end, lower, upper, count);
mergeAndCount(sums, start, mid, end, lower, upper, count);
}
int countRangeSum(int* nums, int numsSize, int lower, int upper) {
long sums[numsSize + 1];
sums[0] = 0;
for (int i = 0; i < numsSize; ++i) {
sums[i + 1] = sums[i] + nums[i];
}
int count = 0;
sortAndCount(sums, 0, numsSize + 1, lower, upper, &count);
return count;
}
int main() {
int nums[] = {-2, 5, -1};
int lower = -2, upper = 2;
printf("%d\n", countRangeSum(nums, 3, lower, upper));
return 0;
}using System;
public class Solution {
public int CountRangeSum(int[] nums, int lower, int upper) {
long[] sums = new long[nums.Length + 1];
for (int i = 0; i < nums.Length; i++)
sums[i + 1] = sums[i] + nums[i];
int count = 0;
SortAndCount(sums, 0, sums.Length, lower, upper, ref count);
return count;
}
private void SortAndCount(long[] sums, int start, int end, int lower, int upper, ref int count) {
if (end - start <= 1) return;
int mid = start + (end - start) / 2;
SortAndCount(sums, start, mid, lower, upper, ref count);
SortAndCount(sums, mid, end, lower, upper, ref count);
int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
int r = 0;
for (int i = start; i < mid; ++i) {
while (j < end && sums[j] - sums[i] < lower) j++;
while (k < end && sums[k] - sums[i] <= upper) k++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r++] = sums[i];
count += k - j;
}
Array.Copy(cache, 0, sums, start, t - start);
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {-2, 5, -1};
int lower = -2, upper = 2;
Console.WriteLine(sol.CountRangeSum(nums, lower, upper));
}
}The Python version employs merge sort with added counting logic, applied on prefix sums. It efficiently identifies sum differences that yield valid sums by merging subarrays and keeping these sums sorted.
Time Complexity: O(n log n)
Space Complexity: O(n)
Approach 3: Default Approach
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, v: number) {
while (x <= this.n) {
this.c[x] += v;
x += x & -x;
}
}
query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
function countRangeSum(nums: number[], lower: number, upper: number): number {
const n = nums.length;
const s = Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
let arr: number[] = Array((n + 1) * 3);
for (let i = 0, j = 0; i <= n; ++i, j += 3) {
arr[j] = s[i];
arr[j + 1] = s[i] - lower;
arr[j + 2] = s[i] - upper;
}
arr.sort((a, b) => a - b);
let m = 0;
for (let i = 0; i < arr.length; ++i) {
if (i === 0 || arr[i] !== arr[i - 1]) {
arr[m++] = arr[i];
}
}
arr = arr.slice(0, m);
const tree = new BinaryIndexedTree(m);
let ans = 0;
for (const x of s) {
const l = search(arr, m, x - upper);
const r = search(arr, m, x - lower);
ans += tree.query(r) - tree.query(l - 1);
tree.update(search(arr, m, x), 1);
}
return ans;
}
function search(nums: number[], r: number, x: number): number {
let l = 0;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l + 1;
}type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
func countRangeSum(nums []int, lower int, upper int) (ans int) {
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
arr := make([]int, (n+1)*3)
for i, j := 0, 0; i <= n; i, j = i+1, j+3 {
arr[j] = s[i]
arr[j+1] = s[i] - lower
arr[j+2] = s[i] - upper
}
sort.Ints(arr)
m := 0
for i := range arr {
if i == 0 || arr[i] != arr[i-1] {
arr[m] = arr[i]
m++
}
}
arr = arr[:m]
tree := newBinaryIndexedTree(m)
for _, x := range s {
l := sort.SearchInts(arr, x-upper) + 1
r := sort.SearchInts(arr, x-lower) + 1
ans += tree.query(r) - tree.query(l-1)
tree.update(sort.SearchInts(arr, x)+1, 1)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Naive Iteration | Time Complexity: O(n^2) |
| Approach 2: Merge Sort with Prefix Sums | Time Complexity: O(n log n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iteration with Prefix Sums | O(n²) | O(n) | Good for understanding the prefix sum transformation or verifying small inputs |
| Merge Sort with Prefix Sums | O(n log n) | O(n) | Best general solution for large arrays and typical interview expectations |
Frequently asked questions
Is Count of Range Sum easy or hard?
Count of Range Sum is classified as a Hard problem because the optimal solution requires combining prefix sums with divide-and-conquer counting. Many candidates initially attempt O(n²) enumeration before recognizing the need for an O(n log n) approach.
Count of Range Sum Python/Java solution
In Python or Java, the typical implementation computes prefix sums and applies a modified merge sort to count valid ranges during the merge phase. The algorithm maintains two pointers in the right half for each left prefix value and counts differences within [lower, upper].
How to solve Count of Range Sum in O(n)?
An exact O(n) solution is not known for the general problem. The best practical approach is O(n log n) using prefix sums with merge sort or balanced data structures such as Binary Indexed Trees or ordered sets to maintain prefix order efficiently.
What is the best approach for Count of Range Sum?
The most efficient approach uses prefix sums combined with a modified merge sort. While sorting the prefix array, the algorithm counts how many prefix differences fall within [lower, upper]. This divide-and-conquer strategy runs in O(n log n) time and O(n) space, which is optimal for large inputs.
Is Count of Range Sum asked at Google/Amazon/Meta?
Count of Range Sum is a classic hard interview problem involving prefix sums and divide-and-conquer counting. Variants of this problem have appeared in interviews at companies like Google, Amazon, and Meta because it tests understanding of advanced array processing and algorithm optimization.
What data structure is used in Count of Range Sum?
The optimized solutions rely on prefix sums along with data structures that maintain sorted order. Common implementations use merge sort, Binary Indexed Trees (Fenwick trees), segment trees, or balanced ordered sets to efficiently count valid prefix ranges.
What is the time complexity of Count of Range Sum?
The optimal algorithm runs in O(n log n) time using a merge-sort-based counting technique on prefix sums. A naive solution that checks every subarray requires O(n²) time, which becomes too slow when the array size grows large.