# 327. Count of Range Sum
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 the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.
# Solution
Approach 1: Merge sort. Build an array of cumulative sum, and convert the problem to find pairs of differences within items of cumulative sum. Recursively sort the items while returning counts.
# Code (Python)
Approach 1:
def countRangeSum(self, nums: list[int], lower: int, upper: int) -> int:
# O(NlogN) idea: mergesort
# build array of cumulative sum, cum_sum can be sorted since we're only interested in the differences of their items
# we want subarrays to be sorted so that it's O(N) to find number of diffs between items in left and item in right
# return counts in subarrays while mergesorting
if not nums:
return 0
if len(nums) == 1:
return 1 if lower <= nums[0] <= upper else 0
cum_sum = [0] # len(cum_sum) == n + 1 to easily handle edge case
for num in nums:
cum_sum.append(num + cum_sum[-1])
# includes 0 but not includes len(cum_sum)
result = self._sort_and_count(cum_sum, 0, len(cum_sum), lower, upper)
return result
def _sort_and_count(self, cum_sum, lo, hi, lower, upper):
mid = (lo + hi) // 2
if mid == lo: # only 1 item, meaning already sorted
return 0
# left side does not include mid, right side does
count = self._sort_and_count(cum_sum, lo, mid, lower, upper) + self._sort_and_count(cum_sum, mid, hi, lower, upper)
i = mid
j = mid
for left in cum_sum[lo:mid]: # mid not included here
# note that i and j keep their position (not reset to mid each time)
# meaning it's still a linear operation even with 2 loops
while i < hi and cum_sum[i] - left < lower:
i += 1
while j < hi and cum_sum[j] - left <= upper:
j += 1
count += (j - i)
# assuming sorted() takes linear time to merge to sorted arrays
cum_sum[lo:hi] = sorted(cum_sum[lo:hi])
return count
# O(N^2) (Time Limit Exceeded): build array of cumulative sum, do pairwise difference
def countRangeSumSlow(self, nums: list[int], lower: int, upper: int) -> int:
if not nums:
return 0
if len(nums) == 1:
return 1 if lower <= nums[0] <= upper else 0
cum_sum = [nums[0]]
for i in range(1, len(nums)):
cum_sum.append(nums[i] + cum_sum[-1])
totals = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
if i == 0:
before = 0
else:
before = cum_sum[i-1]
if lower <= cum_sum[j] - before <= upper:
totals += 1
return totals
# Code (C++)
Approach 1:
class Solution {
private:
int count;
void doMergeSort(vector<long>& sums, int head, int tail, int lower, int upper) {
if (head >= tail)
return;
int mid = head + (tail - head) / 2;
doMergeSort(sums, head, mid, lower, upper);
doMergeSort(sums, mid+1, tail, lower, upper);
vector<int> tmp;
int i1 = head;
int i2 = mid + 1;
int iLower2 = mid + 1;
int iUpper2 = mid + 1;
while (i1 <= mid || i2 <= tail)
{
if (i2 > tail || i1 <= mid && sums[i1] <= sums[i2])
{
while (iLower2 <= tail && sums[iLower2] - sums[i1] < lower)
iLower2++;
while (iUpper2 <= tail && sums[iUpper2] - sums[i1] <= upper)
iUpper2++;
count += iUpper2 - iLower2;
tmp.push_back(sums[i1]);
i1++;
}
else
{
tmp.push_back(sums[i2]);
i2++;
}
}
for (int i = head; i <= tail; ++i)
{
sums[i] = tmp[i-head];
}
}
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
if (n == 0)
return 0;
count = 0;
vector<long> sums;
sums.push_back(0);
for (int i = 0; i < n; ++i)
sums.push_back(sums[i] + nums[i]);
doMergeSort(sums, 0, sums.size()-1, lower, upper);
return count;
}
};