https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/
Based on this intuition, try solving on our own before looking at the code.
Problem statement:
Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.
Example 1:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. Sample Input:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Sample Output: 13
Explanation:
All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4.
After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10].
The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.
Approach 1 (Brute Force):
Let's try to understand "compute the sum of all non-empty continuous subarrays from the array" this part.
Let's look at an example:
{10, 20, 10, 5, 15}
How many continuous subarray are there?
10,
10,20,
10,20,10,
10,20,10,5,
10,20,10,5,15
What about
20,
20,10,
20,10,5,
20,10,5,15
10,
10,5,
10,5,15
5,
5,15
15
If you calculate, you will find there are n * (n + 1) / 2 sub-arrays. And, that is why need a new array of size n * (n + 1) / 2 to store all these subarrays sum.
Next, we need to calculate each subarray sum and store the result in our new array. And we can do that using prefix sum.
Once computed sort the new array.
Get the sum from the new array within range "index left to index right (indexed from 1)". Make sure you modulo the sum with 1000000007 before adding the result.
Time complexity: O(n^2logn)
Space complexity: O(n^2)
Still having trouble you can check the code below:
Solution[Java]:
static int M = 1000000007;
public int rangeSum(int[] nums, int n, int left, int right) {
if(nums.length!=n || left>right){
return -1;
}
int nn = (n*(n+1))/2;
int[] narr = new int[nn];
int k=0;
for(int i=0;i<n;i++){
int sum=0;
for(int j=i;j<n;j++){
sum+=nums[j];
narr[k] = sum;
k++;
}
}
Arrays.sort(narr);
int finalSum = 0;
for(int i=left-1;i<right;i++){
finalSum = (finalSum + narr[i])%M;
}
return finalSum;
}Checkout:
  |
  |
  |
Approach 2(PriorityQueue):
Although the above solution will work for all our test cases but its complexity is quadratic.
Let's see if we can do any better or not.
To understand the next intuition, let's take this example:
nums = [3,2,4,1]
3, =====> 3 {0}
3,2, =====> 5 {0,1}
3,2,4, =====> 9 {0,1,2}
3,2,4,1, =====> 10 {0,1,2,3}
2, =====> 2 {1}
2,4, =====> 6 {1,2}
2,4,1, =====> 7 {1,2,3}
4, =====> 4 {2}
4,1, =====> 5 {2,3}
1, =====> 1 {3}
After sorting them in non-decreasing order we will have something like this: [1, 2, 3, 4, 5, 5, 6, 7, 9, 10].
The sum of the numbers from le = 1 to ri = 5 is 1 + 2 + 3 + 4 + 5 = 15
Now, let's consider this:
nums = [ 3{0}, 2{1}, 4{2}, 1{3} ]
pq = [ 1{3}, 2{1}, 3{0}, 4{2} ]
1{3} [RangeSum = 1]
pq = [ 2{1}, 3{0}, 4{2} ]
2{1} [RangeSum = 1+2]
pq = [ 3{0}, 4{2}, (2,4){2} ]
3{0} [RangeSum = 1+2+3]
pq = [ 4{2}, (3,2){1} ,(2,4){2} ]
4{2} [RangeSum = 1+2+3+4]
pq = [ (3,2){1} , (4,1){3}, (2,4){2} ]
(3,2){1} [RangeSum = 1+2+3+4+5]
pq = [(4,1){3}, (2,4){2}, (3,2,4){2} ]
(4,1){3}
pq = [(2,4){2}, (3,2,4){2} ]
(2,4){2}
pq = [(3,2,4){2}, (2,4,1){3}]
(3,2,4){2}
pq = [(2,4,1){3}, (3,2,4,1){3}]
(2,4,1){3}
pq = [(3,2,4,1){3}]
(3,2,4,1){3}
pq = []
Can you see any pattern here? What if instead of doing all the subarray sum beforehand, we do it while we are sorting them? Yes, we can use something like PriorityQueue, which will help us to do sorting as we process each subarray sum.
First, let's put all the items in the array to a PriorityQueue. But we need to wrap each value with its index before we put them in PriorityQueue. Why do we need an index? You will see in a bit.
Poll the first item from the PriorityQueue which is:
1{3}, 1 is the value at index 3 in nums.
Since it's index is 3, we don't do anything, because as you can see from the previous diagram, the last element of any nums arrays, subarray sum is itself. As this would've been our first item in our sorted subarray sum and our left=1, we will process this value as part of our range sum. Because as we poll() from PriorityQueue, it will give us the lowest value.
Next, poll 2{1} from PriorityQueue. 2 is the value at index 1 of nums array. From the previous diagram, you can see 2 is itself a subarray sum, so we process this for our range sum since this is <=right in sorted subarray sum.
Also, we can form another subarray sum with 4, which is at index 2 of the nums array. So we add 2 and 4 with an updated current index and add in our PriorityQueue.
I hope this clarifies why we need index as well.
As we progress once our index of subarray sum crosses 'right' we will stop and return the range sum.
I hope this clarifies any question you might have about the intuition of this problem.
If you are still struggling with the solution, find the code below for better understanding.
Solution[Java]:
class Pair{
int index;
int sum;
Pair(int i, int s){
index = i;
sum = s;
}
}
class Solution {
static int M = 1000000007;
public int rangeSum(int[] nums, int n, int left, int right) {
PriorityQueue<Pair> pq = new PriorityQueue<>(
new Comparator<Pair>(){
public int compare(Pair o1, Pair o2){
return o1.sum-o2.sum;
}
}
);
for(int i=0;i<n;i++){
pq.offer(new Pair(i, nums[i]));
}
int ans = 0;
for(int i=1;i<=right;i++){
Pair p = pq.poll();
int indexOfSum = p.index;
if(i>=left){
ans = (ans + p.sum)%M;
}
if(indexOfSum<n-1){
pq.offer(
new Pair(indexOfSum+1,p.sum+nums[indexOfSum+1])
);
}
}
return ans;
}
}Time complexity: O(n^2logn)
Space complexity: O(n)
If you don't want to deal with another class, here is another nice and simple one:
static int M = 1000000007;
public int rangeSum(int[] nums, int n, int left, int right) {
PriorityQueue<int[]> pq = new PriorityQueue<>(
new Comparator<int[]>(){
public int compare(int[] o1, int[] o2){
return o1[1]-o2[1];
}
}
);
for(int i=0;i<n;i++){
pq.offer(new int[]{i, nums[i]});
}
int ans = 0;
for(int i=1;i<=right;i++){
int[] p = pq.poll();
int indexOfSum = p[0];
if(i>=left){
ans = (ans + p[1])%M;
}
if(indexOfSum<n-1){
pq.offer(
new int[]{indexOfSum+1,p[1]+nums[indexOfSum+1]}
);
}
}
return ans;
}