Log inSign up
hardLeetCodeNot Started

Count of Range Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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.

A range sum can be expressed as the difference of two prefix sums: S(i, j) = prefix[j + 1] - prefix[i].

Example 1 · Example 1:

Input: nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0, 0] with sum -2, [2, 2] with sum -1, and [0, 2] with sum 2.

Example 2 · Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1
Explanation: The single range [0, 0] has sum 0, which lies in [0, 0].

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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Count of Range Sum.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Count of Range Sum
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Feasible only when n <= 2000.
  • BETTER: Effective when applying Fenwick tree templates for general dynamic range frequency queries.
  • OPTIMAL: The cleanest, fastest, and most memory-efficient approach for range sum count problems.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Nested Loops on Subarrays

Intuition

For every starting index i from 0 to n - 1, maintain a running sum as j goes from i to n - 1. Check if lower <= currentSum <= upper. Because there are O(n2) subarrays, this approach runs in O(n2) time and O(1) space, resulting in Time Limit Exceeded for n = 105.

When to apply: Feasible only when n <= 2000.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: Loop i from 0 to n - 1.
  3. Step 3: Maintain running sum starting at 0, loop j from i to n - 1 adding nums[j].
  4. Step 4: If running sum >= lower and running sum <= upper, increment count.
  5. Step 5: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4int countRangeSumBrute(const std::vector<int>& nums, int lower, int upper) {
5 int n = nums.size();
6 int count = 0;
7 for (int i = 0; i < n; ++i) {
8 long long sum = 0;
9 for (int j = i; j < n; ++j) {
10 sum += nums[j];
11 if (sum >= lower && sum <= upper) {
12 count++;
13 }
14 }
15 }
16 return count;
17}
18
19int main() {
20 std::vector<int> nums = {-2, 5, -1};
21 std::cout << countRangeSumBrute(nums, -2, 2) << std::endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(n^2) where n is the number of elements
  • Space complexity: O(1) auxiliary space

2. Prefix Sums + Fenwick Tree (Binary Indexed Tree)

Intuition

Express the condition as: $\text{lower} <= \text{prefix}[j] - \text{prefix}[i] <= \text{upper} \iff \text{prefix}[j] - \text{upper} <= \text{prefix}[i] <= \text{prefix}[j] - \text{lower} For each prefix sum \text{prefix}[j] (j >= 1), we need to count how many previous prefix sums \text{prefix}[i] (i < j) satisfy this inequality. 1. Collect all candidate values: \text{prefix}[k], \text{prefix}[k] - \text{upper}, and \text{prefix}[k] - \text{lower}. 2. Coordinate compress all unique candidate values into indices [1 \dots M]. 3. Iterate j from 0 to n: - For j > 0, query the Fenwick tree for the count of numbers in the range [\text{prefix}[j] - \text{upper}, \text{prefix}[j] - \text{lower}]. - Insert \text{prefix}[j] into the Fenwick tree. 4. Total runtime is O(n log n) with O(n)$ space.

When to apply: Effective when applying Fenwick tree templates for general dynamic range frequency queries.

Algorithm

  1. Step 1: Compute prefix sums of nums.
  2. Step 2: Collect all prefix[i], prefix[i] - upper, and prefix[i] - lower into a values list.
  3. Step 3: Sort and deduplicate values to build coordinate compression mapping.
  4. Step 4: Initialize a Fenwick tree of size equal to unique compressed values.
  5. Step 5: Insert prefix[0]=0 into Fenwick tree. For each prefix[i], query count in [prefix[i] - upper, prefix[i] - lower], add to answer, then insert prefix[i].
  6. Step 6: Return answer count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct BIT {
6 int n;
7 std::vector<int> tree;
8 BIT(int n) : n(n), tree(n + 1, 0) {}
9 void add(int i, int delta) {
10 for (; i <= n; i += i & -i) tree[i] += delta;
11 }
12 int query(int i) {
13 int sum = 0;
14 for (; i > 0; i -= i & -i) sum += tree[i];
15 return sum;
16 }
17 int queryRange(int l, int r) {
18 if (l > r) return 0;
19 return query(r) - query(l - 1);
20 }
21};
22
23int countRangeSumBIT(const std::vector<int>& nums, int lower, int upper) {
24 int n = nums.size();
25 std::vector<long long> prefix(n + 1, 0);
26 for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + nums[i];
27
28 std::vector<long long> allVals;
29 for (long long x : prefix) {
30 allVals.push_back(x);
31 allVals.push_back(x - upper);
32 allVals.push_back(x - lower);
33 }
34 std::sort(allVals.begin(), allVals.end());
35 allVals.erase(std::unique(allVals.begin(), allVals.end()), allVals.end());
36
37 auto getRank = [&](long long val) {
38 return std::lower_bound(allVals.begin(), allVals.end(), val) - allVals.begin() + 1;
39 };
40
41 BIT bit(allVals.size());
42 bit.add(getRank(0), 1);
43 int ans = 0;
44
45 for (int i = 1; i <= n; ++i) {
46 int leftRank = getRank(prefix[i] - upper);
47 int rightRank = getRank(prefix[i] - lower);
48 ans += bit.queryRange(leftRank, rightRank);
49 bit.add(getRank(prefix[i]), 1);
50 }
51
52 return ans;
53}
54
55int main() {
56 std::vector<int> nums = {-2, 5, -1};
57 std::cout << countRangeSumBIT(nums, -2, 2) << std::endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(n log n) time due to sorting and BIT operations
  • Space complexity: O(n) auxiliary space for coordinates and BIT

3. Divide and Conquer (Merge Sort on Prefix Sums)

Intuition

Let P be the array of prefix sums: P[0] = 0, P[1] = nums[0], \dots, P[n] = \sum_{0}^{n-1} nums. We want to count pairs (i, j) with i < j such that lower <= P[j] - P[i] <= upper. This structure mirrors counting inversions with Merge Sort: 1. Divide prefix sums into left half P[low \dots mid] and right half P[mid + 1 \dots high]. 2. Recursively count valid pairs and sort both halves. 3. During the merge step: - For each element P[j] in the right half (j \in [mid + 1, high]): - Maintain two pointers in the left half, p1 and p2: - p1 is the first index such that P[j] - P[p1] <= upper. - p2 is the first index such that P[j] - P[p2] < lower. - Because the left half is sorted, both p1 and p2 only move monotonically forward! - The number of valid pairs for this P[j] is exactly p2 - p1. 4. Merge the two sorted halves into temporary buffer. 5. Overall runtime is O(n log n), with minimal constant factors, zero tree allocations, and cache-friendly contiguous reads.

When to apply: The cleanest, fastest, and most memory-efficient approach for range sum count problems.

Algorithm

  1. Step 1: Compute prefix sums array prefix of length n + 1.
  2. Step 2: Define mergeSort(left, right) which counts valid pairs and sorts prefix[left..right].
  3. Step 3: Base case: if left >= right return 0.
  4. Step 4: Compute mid = (left + right) / 2 and recursively call on [left, mid] and [mid + 1, right].
  5. Step 5: For each j in [mid + 1, right], slide p1 until prefix[j] - prefix[p1] <= upper, and slide p2 until prefix[j] - prefix[p2] < lower. Add p2 - p1 to count.
  6. Step 6: Merge the two sorted subarrays in O(right - left) time and return total count.

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Compute prefix sums of [-2, 5, -1]: prefix = [0, -2, 3, 2]
Visual state
Values and pointers at this exact step
pointers
S
0
-2
3
2
0
↑ left
1
↑ mid
2
3
↑ right
Check / comparison
Split prefix into left=[0, -2] and right=[3, 2]
Decision / next transition
Recursively solve left and right halves
Why this step matters

Compute prefix sums of [-2, 5, -1]: prefix = [0, -2, 3, 2]. Range target: lower = -2, upper = 2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4int mergeSortCount(std::vector<long long>& prefix, int left, int right, int lower, int upper, std::vector<long long>& temp) {
5 if (left >= right) return 0;
6 int mid = left + (right - left) / 2;
7 int count = mergeSortCount(prefix, left, mid, lower, upper, temp) +
8 mergeSortCount(prefix, mid + 1, right, lower, upper, temp);
9
10 int p1 = left, p2 = left;
11 for (int j = mid + 1; j <= right; ++j) {
12 while (p1 <= mid && prefix[j] - prefix[p1] > upper) p1++;
13 while (p2 <= mid && prefix[j] - prefix[p2] >= lower) p2++;
14 count += (p2 - p1);
15 }
16
17 // Standard merge
18 int i = left, j = mid + 1, k = left;
19 while (i <= mid && j <= right) {
20 if (prefix[i] <= prefix[j]) temp[k++] = prefix[i++];
21 else temp[k++] = prefix[j++];
22 }
23 while (i <= mid) temp[k++] = prefix[i++];
24 while (j <= right) temp[k++] = prefix[j++];
25 for (int idx = left; idx <= right; ++idx) prefix[idx] = temp[idx];
26
27 return count;
28}
29
30int countRangeSum(std::vector<int>& nums, int lower, int upper) {
31 int n = nums.size();
32 std::vector<long long> prefix(n + 1, 0);
33 for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + nums[i];
34 std::vector<long long> temp(n + 1);
35 return mergeSortCount(prefix, 0, n, lower, upper, temp);
36}
37
38int main() {
39 std::vector<int> nums = {-2, 5, -1};
40 std::cout << countRangeSum(nums, -2, 2) << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(n log n) time
  • Space complexity: O(n) auxiliary space for merge sort buffer

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Nested Loops on SubarraysO(n^2) where n is the number of elementsO(1) auxiliary spaceEvaluate the sum of every possible subarray (i, j) and count how many sums fall within [lower, upper].O(n2) where n is the number of elements
2.Prefix Sums + Fenwick Tree (Binary Indexed Tree)O(n log n) time due to sorting and BIT operationsO(n) auxiliary space for coordinates and BITDiscretize prefix sum boundaries and query intervals [prefix[j] - upper, prefix[j] - lower] using a Fenwick tree.O(n log n) time due to sorting and BIT operations
3.Divide and Conquer (Merge Sort on Prefix Sums)OptimalO(n log n) timeO(n) auxiliary space for merge sort bufferSort prefix sums via merge sort. While merging left and right halves, use two monotone sliding pointers to count valid pairs in O(n log n).O(n log n) time

Common Pitfalls & Crucial Edge Cases

32-bit integer overflow

Forgetting to declare prefix sums as long long in C++ or long in Java.

Off-by-one in prefix sum array size

Prefix sum array MUST have size N + 1 with prefix[0] = 0 to account for subarrays starting at index 0.

O(N^2) brute force

Evaluating all subarrays takes O(N2) and triggers TLE for N = 105.

Crucial Edge Cases to Validate:

  • Single element array `nums = [0], lower = 0, upper = 0` — Single range sum 0 fits in [0, 0]; returns 1.
  • Prefix sum overflow — Must use 64-bit integers for all prefix computations.
  • lower == upper — Exact range sum required.
  • No valid range sums exist — Returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Transform the range condition algebraically: show how S(i, j) in [lower, upper] translates to window bounds on earlier prefix sums.
  2. Explain the Merge Sort approach: because both sub-arrays are sorted, two sliding pointers traverse monotonically without resetting.
  3. Discuss the alternative Fenwick Tree / Segment Tree with coordinate compression approach.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How can the range sum S(i, j) = lower <= sum(nums[i..j]) <= upper be expressed using prefix sums?

2.What algorithm counts these prefix sum pairs in O(N log N) time?

3.Why must prefix sums be stored as 64-bit integers (long long in C++)?

Back to DSA Sheet