Problem

You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted 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.

Examples

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.

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Solution

Video Explanation

Please refer to the video below:

Method 1 - Naive Approach

To solve this problem, we’ll first need to compute the sum of all non-empty continuous subarrays, then sort the resulting sums, and finally determine the sum of a specified range of these sorted subarrays. Given the potential size of the array and the need for efficiency, here’s a step-by-step approach:

Approach:

  1. Compute All Subarray Sums:
    • Compute the sum of all non-empty continuous subarrays from the input array.
    • Store these sums in a list.
  2. Sort the Subarray Sums:
    • Sort the list of subarray sums in non-decreasing order.
  3. Compute the Sum of a Specific Range:
    • Sum the elements in the list from the left to right indices (inclusive).
  4. Modulo Operation:
    • Since the result can be very large, take the sum modulo (10^9 + 7).

Code

Java
class Solution {

	public int rangeSum(int[] nums, int n, int left, int right) {
		final int MOD = 1_000_000_007;

		List<Integer> subarraySums = new ArrayList<>();

		// Compute all subarray sums
		for (int i = 0; i < nums.length; i++) {
			int currentSum = 0;

			for (int j = i; j < nums.length; j++) {
				currentSum += nums[j];
				subarraySums.add(currentSum);
			}
		}

		// Sort the sums
		Collections.sort(subarraySums);

		// Compute the sum of the required range
		long ans = 0;

		for (int i = left - 1; i < right; i++) {
			ans = (ans + subarraySums.get(i)) % MOD;
		}

		return (int) ans;
	}

}
Python
class Solution:
	def range_sum(self, nums: List[int], n: int, left: int, right: int) -> int:
	    MOD = 1_000_000_007
	    subarray_sums = []
	
	    # Compute all subarray sums
	    for i in range(n):
	        current_sum = 0
	        for j in range(i, n):
	            current_sum += nums[j]
	            subarray_sums.append(current_sum)
	
	    # Sort the subarray sums
	    subarray_sums.sort()
	
	    # Compute the sum of the specified range
	    result = sum(subarray_sums[left - 1 : right]) % MOD
	
	    return result

Complexity

  • ⏰ Time complexity: O(n^2 log n) where is n is length of input array
    • Generating subarray takes O(n^2)
    • Sorting takes O(m log m) where m = n*(n+1)/2
    • Summing takes O(right - left), in worst case O(n)
  • 🧺 Space complexity: O(n^2)

Dry Run

Compute all subarrays

Loop through starting index i and ending index j to compute all possible subarray sums.

  • For i = 0, generate subarrays starting from index 0:
    • j = 0: currentSum = 1 → Add 1 to subarraySums
    • j = 1: currentSum = 1 + 2 = 3 → Add 3 to subarraySums
    • j = 2: currentSum = 1 + 2 + 3 = 6 → Add 6 to subarraySums
    • j = 3: currentSum = 1 + 2 + 3 + 4 = 10 → Add 10 to subarraySums
  • For i = 1, generate subarrays starting from index 1:
    • j = 1: currentSum = 2 → Add 2 to subarraySums
    • j = 2: currentSum = 2 + 3 = 5 → Add 5 to subarraySums
    • j = 3: currentSum = 2 + 3 + 4 = 9 → Add 9 to subarraySums
  • For i = 2, generate subarrays starting from index 2:
    • j = 2: currentSum = 3 → Add 3 to subarraySums
    • j = 3: currentSum = 3 + 4 = 7 → Add 7 to subarraySums
  • For i = 3, generate subarrays starting from index 3:
    • j = 3: currentSum = 4 → Add 4 to subarraySums

subarraySums becomes:

subarraySums = [1, 3, 6, 10, 2, 5, 9, 3, 7, 4]
Sort the subarraySums
subarraySums = [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]
Compute the sum between the range

Sum the elements from index left - 1 = 0 to right - 1 = 4 inclusive.

ans = sum(subarraySums[left - 1:right]) % MOD
		= (1 + 2 + 3 + 3 + 4) % 1_000_000_007 = 13

Method 2 - Using Heap with Sum and Index pair

We can add pair to priority queue, with sum and index. Where sum = nums[i] + ... + nums[j], and index = j + 1. The reason for this is, lets look at subarraySums, corresponding to index + 1:

[1], [1, 2], [1, 2, 3] => [1, 3, 6]
[2], [2, 3] => [2, 5]
[3] => [3]

So, we can pop out pair from minHeap and add it back if index + 1 < n. This is similar to Generate Kth Ugly Number.

Here are the steps we can take:

Code

Java
class Solution {
    int MOD = 1_000_000_007;
    
    static class Pair{
        long sum;
        int index;
        public Pair(int sum, int index){
            this.sum = sum;
            this.index = index;
        }
    }
    
    public int rangeSum(int[] nums, int n, int left, int right) {
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>((a, b) -> Long.compare(a.sum, b.sum));
        for (int i = 0; i < n; i++) {
            pq.offer(new Pair(nums[i], i + 1));
        }
		
        int ans = 0;
        for (int i = 1; i <= right; i++) {
            Pair curr = pq.poll();
            if (i >= left) {
                ans = (int) ((curr.sum + ans) % MOD);
            }
            if (curr.index < n) {
                curr.sum += nums[curr.index];
				curr.index += 1;
                pq.offer(curr);
            }
        }
        return ans;
    }
}
Python
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        h = [(x, i) for i, x in enumerate(nums)] #min-heap 
        heapify(h)
        
        ans = 0
        for k in range(1, right+1): #1-indexed
            x, i = heappop(h)
            if k >= left: ans += x
            if i+1 < len(nums): 
                heappush(h, (x + nums[i+1], i+1))
                
        return ans % 1_000_000_007

Complexity

  • ⏰ Time complexity: O(right * log n)
  • 🧺 Space complexity: O(n)

Dry Run

Initial Pairs

Insert initial pairs into the priority queue: [ (1,1), (2,2), (3,3), (4,4) ]

Processing
Iteration 1
  • Pop the smallest sum: (1,1)
  • Since i = 1 is between left and right, add (1,1) sum to ans.
    • ans = (0 + 1) % MOD = 1
  • Push next sum: (1+2, 2) = (3,2)
  • Queue now: [ (2,2), (3,2), (3,3), (4,4) ]
Iteration 2
  • Pop the smallest sum: (2,2)
  • Since i = 2 is between left and right, add (2,2) sum to ans.
    • ans = (1 + 2) % MOD = 3
  • Push next sum: (2+3, 3) = (5,3)
  • Queue now: [ (3, 2), (4, 4), (3, 3), (5, 3) ]
Iteration 3
  • Pop the smallest sum: (3, 2)
  • Since i = 3 is between left and right, add (3, 2) sum to ans.
    • ans = (3 + 3) % MOD = 6
  • Push next sum: (3 + 3 = 6, 3)
  • Queue now: [(3, 3), (4, 4), (5, 3), (6, 3)]
Iteration 4
  • Pop the smallest sum: (3, 3)
  • Since i = 4 is between left and right, add (3, 3) sum to ans.
    • ans = (6 + 3) % MOD = 9
  • Push next sum: (3 + 4 = 7, 4)
  • Queue now: [(4, 4), (6, 3), (5, 3), (7, 4)]
Iteration 5
  • Pop the smallest sum: (4, 4)
  • Since i = 5 is between left and right, add (4, 4) sum to ans.
    • ans = (9 + 4) % MOD = 13
  • Queue now: [(5, 3), (6, 3), (7, 4)] (Nothing to push as index of Node(4) has reached n=4)
Final Results
ans = 13