Introduction
LeetCode 327: Count of Range Sum asks us to count the number of subarrays whose sums fall within a given range [lower, upper].
This is not a straightforward sliding window problem — due to the need to count all possible subarrays, we need an optimized O(n log n) approach.
The trick? Use prefix sums and a modified merge sort to count valid pairs efficiently.
Problem Statement
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of elements in nums[i..j], inclusive.
Example
python
Input: nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3
Explanation:
The 3 valid subarrays are:
[-2], [-2, 5, -1], [5, -1]
✅ Approach: Prefix Sum + Modified Merge Sort
Step-by-Step Explanation
🧩 Step 1: Prefix Sums
Let prefix_sums[i] be the sum of nums[0] to nums[i - 1].
- For a subarray
nums[i..j], its sum is prefix_sum[j + 1] - prefix_sum[i]
- We count pairs
(i, j) such that:
lua
lower <= prefix_sum[j+1] - prefix_sum[i] <= upper
🧩 Step 2: Count While Merging (Like Merge Sort)
- Sort the prefix sums.
- While merging, count how many elements from the right half satisfy the range condition for each element in the left half.
- Use two pointers to keep the counting in
O(n) during merge.
✅ Python Code
python
class Solution:
def countRangeSum(self, nums: list[int], lower: int, upper: int) -> int:
def merge_sort(lo, hi):
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
count = merge_sort(lo, mid) + merge_sort(mid, hi)
j = k = t = mid
cache = []
for i in range(lo, mid):
# count the number of valid j's
while k < hi and prefix_sums[k] - prefix_sums[i] < lower:
k += 1
while j < hi and prefix_sums[j] - prefix_sums[i] <= upper:
j += 1
count += j - k
# merge the two halves
while t < hi and prefix_sums[t] < prefix_sums[i]:
cache.append(prefix_sums[t])
t += 1
cache.append(prefix_sums[i])
prefix_sums[lo:lo+len(cache)] = cache
return count
prefix_sums = [0]
for num in nums:
prefix_sums.append(prefix_sums[-1] + num)
return merge_sort(0, len(prefix_sums))
🧪 Dry Run Example
Input: nums = [-2, 5, -1], lower = -2, upper = 2
Prefix Sums: [0, -2, 3, 2]
Valid subarrays:
[-2] = -2[5, -1] = 4 ❌[-2, 5] = 3 ❌[-2, 5, -1] = 2 ✅[5] = 5 ❌[-1] = -1 ✅
Count = 3
⏱️ Time & Space Complexity
MetricValueTime ComplexityO(n log n)Space ComplexityO(n)
🧠 Key Takeaways
- Prefix sums simplify subarray sum problems.
- Modified merge sort lets us count valid ranges efficiently.
- This divide-and-conquer technique avoids O(n²) brute force.
🧱 Edge Cases
- Empty input → return 0
- All zeros and
lower = 0, upper = 0 → multiple subarrays
- Negative and positive mixed values
✅ Conclusion
LeetCode 327: Count of Range Sum is an advanced-level problem that’s often used in interviews to assess a candidate’s understanding of divide and conquer, prefix sums, and efficient counting algorithms.
Mastering this technique opens doors to solving many difficult range problems efficiently.