Leetcode 1508. Range Sum of Sorted Subarray Sums
Problem Explanation
Given an array consisting of positive integers, we are to compute the sum of all non-empty continuous subarrays. The subarrays are computed such that the element of each subarray would be distinct and sorted in non-decreasing order after which a new array is created. The problem is to find the sum of the numbers from index left to index right in the newly sorted array. Given the number can be extremely large, we are to output the result modulo 1,000,000,007.
To find the solution, the algorithm we would implement is the Binary Search Technique in order to find the first K Subarray Sums. A helper function will be used to compute the sum of subarrays that don't exceed the given limit and the number of these subarrays. To compute these subarrays, a moving window technique is used. For each subarray, we will keep track of the current sum and add the product of the number of elements and its last element to this sum. If the window sum exceeds the limit, the window is shrunk from the left side.
For example, given Nums = [1, 2, 3, 4, 5], Left = 1, Right = 5, the result should be 21
Python Solution
1 2python 3class Solution: 4 def rangeSum(self, nums, n, left, right) -> int: 5 kMod = 1_000_000_007 6 def subarraysAndSumNoGreaterThan(m): 7 count = 0 8 total = 0 9 sum = 0 10 window = 0 11 i = 0 12 j = 0 13 while j < n: 14 sum += nums[j] * (j - i + 1) 15 window += nums[j] 16 while window > m: 17 sum -= window 18 window -= nums[i] 19 i += 1 20 count += j - i + 1 21 total += sum 22 j += 1 23 return count, total 24 # L, R is the possible range of the sum of any subarray 25 L = min(nums) 26 R = sum(nums) 27 def firstKSubarraysSum(k) -> int: 28 l = L 29 r = R 30 while l < r: 31 m = l + (r - l) // 2 32 if subarraysAndSumNoGreaterThan(m)[0] < k: 33 l = m + 1 34 else: 35 r = m 36 count, total = subarraysAndSumNoGreaterThan(l) 37 return total - l * (count - k) 38 return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1)) % kMod
Citation
This problem is referenced from https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/.# JavaScript Solution
The JavaScript solution uses similar logic to the Python solution, utilizing a binary search technique to find the first K subarray sums. A helper function getSubarraysSumNoGreaterThan(target)
is used to calculate the sum of all the subarray sums and the number of these subarrays that do not exceed the target.
1 2javascript 3class Solution { 4 rangeSum(nums, n, left, right) { 5 const MOD = 1e9 + 7; 6 let prefixSum = new Array(n + 1).fill(0); 7 for (let i = 1; i <= n; i++) { 8 prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; 9 } 10 11 let getSubarraysSumNoGreaterThan = (target) => { 12 let subarraysSum = 0, curSum = 0; 13 let count = 0, j = 1; 14 for (let i = 1; i <= n; i++) { 15 while (j <= n && prefixSum[j] - prefixSum[i - 1] <= target) { 16 curSum += prefixSum[j] - prefixSum[i - 1]; 17 j++; 18 } 19 subarraysSum += curSum + (j - i) * (prefixSum[i - 1] - target); 20 subarraysSum %= MOD; 21 count += j - i; 22 curSum -= prefixSum[j - 1] - prefixSum[i]; 23 } 24 return {count, subarraysSum}; 25 } 26 27 let firstKSubarraysSum = (k) => { 28 let l = Math.min(...nums), r = prefixSum[n], m; 29 while (l < r) { 30 m = l + ((r - l) >> 1); 31 let {count, subarraysSum} = getSubarraysSumNoGreaterThan(m); 32 if (count < k) { 33 l = m + 1; 34 } else { 35 r = m; 36 res = subarraysSum; 37 } 38 } 39 return res; 40 } 41 return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1) + MOD) % MOD; 42 } 43}
Java Solution
Below is the Java version of this solution:
1 2java 3import java.util.PriorityQueue; 4import java.util.Queue; 5 6public class Solution { 7 private static final int MODULO = 1_000_000_007; 8 9 public int rangeSum(int[] nums, int n, int left, int right) { 10 Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); 11 for (int i = 0; i < n; i++) { 12 pq.offer(new int[]{nums[i], i + 1}); 13 } 14 int sum = 0; 15 for (int i = 1; i <= right; i++) { 16 int[] entry = pq.poll(); 17 if (i >= left) { 18 sum = (sum + entry[0]) % MODULO; 19 } 20 if (entry[1] < n) { 21 pq.offer(new int[]{entry[0] + nums[entry[1]], entry[1] + 1}); 22 } 23 } 24 return sum; 25 } 26}
In the Java solution, we utilize a PriorityQueue
to keep track of the sums of the subarrays. For each number, we put it and its next index into the queue. For each smallest sum, we remove it from the queue, add it to the total sum if it's in the range, and add the next sum into the queue if possible. The sum is then returned modulo 1,000,000,007 to prevent overflow.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.