Skip to main content

Count of Range Sum


Given an array nums of integers, 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.

How many range sums lie in the inclusive range [lower, upper]?

Example 1


all//Count of Range

def countRangeSum(nums, lower, upper):
res = 0
prefix_sum = [0]
for num in nums:
prefix_sum.append(prefix_sum[-1] + num)
# sort the prefix_sum array
sorted_prefix_sum = sorted(prefix_sum)
# use two pointer to scan the sorted_prefix_sum array
j = 0
for i in range(len(sorted_prefix_sum)):
while j < len(sorted_prefix_sum) and sorted_prefix_sum[j] - sorted_prefix_sum[i] < lower:
j += 1
k = j
while k < len(sorted_prefix_sum) and sorted_prefix_sum[k] - sorted_prefix_sum[i] <= upper:
k += 1
res += k - j
return res