Divide & Conquer — Count of Range Sum
↗ LeetCode: Count of Range Sum · Hard · pattern chapter →
Asked atGoogleAmazon
Count subarrays whose sum lies in [lower, upper] (inclusive).
Example 1 — nums=[-2,5,-1], lower=-2, upper=2 → 3Example 2 — nums=[0], lower=0, upper=0 → 1
Constraints — 1 ≤ n ≤ 10⁵; -2³¹ ≤ nums[i] ≤ 2³¹−1. Brute enumerates every (i, j) pair — O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Merge-sort D&C with two-pointer range count is O(n log n) = 1.7·10⁶ ops = <20 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — All subarrays
O(n²). Baseline.
Approach 2 — Merge sort on prefix sums (canonical)
Insight. Sum of [i, j] = pref[j+1] - pref[i]. Count pairs (i, j) with lower ≤ pref[j] - pref[i] ≤ upper and i < j. During merge sort of pref, whenever left half's element L and right half's element R maintain L < R in the original sequence, count valid L, Rs via two pointers.
java
int countRangeSum(int[] nums, int lower, int upper) {
long[] pref = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) pref[i + 1] = pref[i] + nums[i];
return mergeCount(pref, 0, pref.length, lower, upper);
}
int mergeCount(long[] p, int lo, int hi, int lower, int upper) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
int count = mergeCount(p, lo, mid, lower, upper) + mergeCount(p, mid, hi, lower, upper);
int i = mid, j = mid;
for (int k = lo; k < mid; k++) {
while (i < hi && p[i] - p[k] < lower) i++;
while (j < hi && p[j] - p[k] <= upper) j++;
count += j - i;
}
long[] merged = new long[hi - lo];
int a = lo, b = mid, w = 0;
while (a < mid && b < hi) merged[w++] = p[a] <= p[b] ? p[a++] : p[b++];
while (a < mid) merged[w++] = p[a++];
while (b < hi) merged[w++] = p[b++];
System.arraycopy(merged, 0, p, lo, merged.length);
return count;
}Execution Trace
Complexity — Time O(n log n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| All subarrays | O(n²) | O(n) | baseline |
| Merge sort | O(n log n) | O(n) | canonical |
When to use which
- Count pairs with range constraint on transformed values → merge sort.
- Fenwick/BIT alternative → compress prefix values; count during single sweep.
- Segment tree → same asymptotics; different implementation.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems