LC 0327 [H] Count of Range Sum - ALawliet/algorithms GitHub Wiki
With Divide and Conquer, you first suppose you sovled two halves of array fisrt[i] = sum (0..i) and counted the possible qualified ranges (sum of subarray of [lower, upper]) in each half. Then if you find all the qualified range crossing left half and right half then you complete the answer.
Note you’ve already sorted first[i] in left half and right half. You pick a left element of first array in left half, call it “left”. And you then pick a right in right half. For each left: Right – left is a range sum across left half and right half. Check it meet [lower, upper] or not. If the range sum is too small? Simply increase right. Too large? Stop, you don’t need to increase right pointer anymore, because first is sorted and increasing right can only make the sum larger.
Therefore for each left, you
find min right index (i) that meets right – left >= lower,
find max right index (j) that meets right – left > upper,
the j – i is the number of valid range sums. Then you iterate next left and search the according answer.
A side note is when left increase one element, the right-left can only become smaller, what you only need to do is increase right to find larger range sum so that it is valid. Therefore the two loops only takes linear time.
class Solution:
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
def count(nums):
if not nums:
return 0
if len(nums) == 1:
return lower <= nums[0] <= upper
m = len(nums) // 2
left = nums[:m]
right = nums[m:]
ans = count(left) + count(right)
# This part is searching for all compounds of the left with the right part.
# Start from the middle, accumulate left array from right to left, and right array from left to right.
# Sample: [5, -2, -1, 3] --> acc_left: [3, -2], acc_right: [-1, 2]
#
# With each prefix sum in the right part, we search for all possible suffix sums in the left part to have the final sum
# in [lower, upper]. This can be done by a binary search after sorting the prefix sum of the left part. We don't
# need to care about the original position of the sum this time.
acc_left = sorted(accumulate(left[::-1]))
acc_right = list(accumulate(right))
for r in acc_right:
ans += bisect_right(acc_left, upper - r) - bisect_left(acc_left, lower - r)
return ans
return int(count(nums))
# prefix-sum + merge-sort | time complexity: O(nlogn)
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
prefixsums = [0]
for x in nums:
prefixsums.append(prefixsums[-1] + x)
# inclusive
def mergesort(A,l,r):
if l >= r:
return 0
m = (l+r) // 2
count = mergesort(A,l,m) + mergesort(A,m+1,r)
i = j = m+1
# O(n)
for left in A[l:m+1]: # left half
while i <= r and A[i] - left < lower: i += 1
while j <= r and A[j] - left <= upper: j += 1
count += j-i
A[l:r+1] = sorted(A[l:r+1])
return count
return mergesort(prefixsums, 0, len(prefixsums) - 1)
'''
First compute the prefix sums: first[m] is the sum of the first m numbers.
Then the sum of any subarray nums[i:k] is simply first[k] - first[i].
So we just need to count those where first[k] - first[i] is in [lower,upper].
To find those pairs, I use mergesort with embedded counting. The pairs in the left half and the pairs in the right half get counted in the recursive calls. We just need to also count the pairs that use both halves.
For each left in first[lo:mid] I find all right in first[mid:hi] so that right - left lies in [lower, upper]. Because the halves are sorted, these fitting right values are a subarray first[i:j]. With increasing left we must also increase right, meaning must we leave out first[i] if it's too small and and we must include first[j] if it's small enough.
Besides the counting, I also need to actually merge the halves for the sorting. I let sorted do that, which uses Timsort and takes linear time to recognize and merge the already sorted halves.
'''
def countRangeSum(self, nums, lower, upper):
first = [0]
for num in nums:
first.append(first[-1] + num)
def sort(lo, hi):
mid = (lo + hi) // 2
if mid == lo:
return 0
count = sort(lo, mid) + sort(mid, hi)
i = j = mid
for left in first[lo:mid]:
while i < hi and first[i] - left < lower: i += 1
while j < hi and first[j] - left <= upper: j += 1
count += j - i
# print(first[lo:hi], sorted(first[lo:hi]))
# first[lo:hi] = sorted(first[lo:hi])
first[lo:hi] = heapq.merge(first[lo:mid], first[mid:hi])
return count
return sort(0, len(first))
'''
First compute the prefix sums: first[m] is the sum of the first m numbers.
Then the sum of any subarray nums[i:k] is simply first[k] - first[i].
So we just need to count those where first[k] - first[i] is in [lower,upper].
To find those pairs, I use mergesort with embedded counting. The pairs in the left half and the pairs in the right half get counted in the recursive calls. We just need to also count the pairs that use both halves.
For each left in first[lo:mid] I find all right in first[mid:hi] so that right - left lies in [lower, upper]. Because the halves are sorted, these fitting right values are a subarray first[i:j]. With increasing left we must also increase right, meaning must we leave out first[i] if it's too small and and we must include first[j] if it's small enough.
Besides the counting, I also need to actually merge the halves for the sorting. I let sorted do that, which uses Timsort and takes linear time to recognize and merge the already sorted halves.
'''
# prefix-sum + hashmap | time complexity: O(n+(upper-lower+1)*n) => TLE
# def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
# cumsum = [0]
# for n in nums:
# cumsum.append(cumsum[-1]+n)
# import collections
# record = collections.defaultdict(int)
# res = 0
# for csum in cumsum:
# for target in range(lower,upper+1):
# if csum - target in record:
# res += record[csum - target]
# record[csum] +=1
# return res