Range Sum of Sorted Subarray Sums

Try to solve the Range Sum of Sorted Subarray Sums problem.

We'll cover the following

Statement

You are given an integer array nums containing nn positive integers along with left and right. Calculate the sum of its elements for every non-empty continuous subarray of nums. Collect these sums into a new array and sort it in nondecreasing order. This will result in a new array of size n×(n+1)/2n \times (n + 1) /2.

Your task is to return the sum of the elements in this sorted array from the index left to right (inclusive with 1-based indexing).

Note: As the result can be large, return the sum modulo 109+710^9 + 7.

Constraints:

  • n=n = nums.length

  • 1≤1 \leq nums.length ≤1000\leq 1000

  • 1≤1 \leq nums[i] ≤100\leq 100

  • 1≤1 \leq left ≤\leq right ≤n×(n+1)/2\leq n \times (n + 1) / 2

Examples

Press + to interact
canvasAnimation-image
1 of 3

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Range Sum of Sorted Subarray Sums

1

For the input nums = [3, 5, 2], what is the sum of elements between indexes left = 3 and right = 6 in the sorted subarray sums?

A)

9

B)

10

C)

30

D)

14

Question 1 of 30 attempted

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Try it yourself

Implement your solution in the following coding playground.

Press + to interact
Java
usercode > Solution.java
import java.util.*;
public class Solution {
    public static int rangeSum(int[] nums, int n, int left, int right) {
        // Replace the following placeholder return statement with your code
        return -1;
    }
}
Range Sum of Sorted Subarray Sums

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.