1508. Range Sum of Sorted Subarray Sums


Problem Description

The given problem revolves around finding the sum of a specific subset of a sorted array that contains sums of all non-empty continuous subarrays of the given array nums. The problem requires three inputs:

  1. nums - an array of n positive integers.
  2. left - the starting index from which to sum (one-indexed).
  3. right - the ending index up to which to sum (one-indexed).

Our objective is to compute the sum of all non-empty continuous subarrays, sort these sums, and then calculate the sum of the elements from the left to right indices in the sorted array. The final answer should be returned modulo 10^9 + 7 to handle very large numbers which could cause integer overflow situations.

To clarify:

  • A non-empty continuous subarray is a sequence of one or more consecutive elements from the array.
  • Sorting these sums means arranging them in non-decreasing order.
  • Summing from index left to index right implies adding all elements of the sorted sums array starting at index left-1 and ending at index right-1 (since the problem statement indexes from 1, but arrays in most programming languages, including Python, are 0-indexed).

Intuition

The brute force approach to this problem is to generate all possible continuous subarrays of nums, calculate their sums, and then sort these sums. This can be done by using two nested loops:

  1. The outer loop goes through each element of nums from which a subarray can start.
  2. The inner loop extends the subarray from the starting element from the outer loop to the end of nums, calculating the sum for each extension.

This generates an array arr of sums for each subarray. Once we have this array, we sort it. With the sorted array, we now only need to sum the numbers from left-1 to right-1 since we're using Python's zero-indexing (the original problem indexes from 1).

This solution is intuitive but not optimized. It can solve the problem as long as the nums array is not too large since the time complexity would otherwise become prohibitive. For larger arrays, an optimized approach should be considered involving more advanced techniques such as prefix sums, heaps, or binary search. However, for the provided solution, we stick to the intuitive brute force method, being mindful of its limitations.

Solution Approach

The provided solution iterates through each possible subarray of the given array nums and maintains a running sum. To achieve this, the following steps are implemented:

  1. Initialize an empty list arr that will hold the sums of all non-empty continuous subarrays.

  2. Use a nested loop to iterate through all possible subarrays:

    • The outer loop, controlled by variable i, goes from 0 to n-1, where i represents the starting index of a subarray.
    • For each i, initialize a sum variable s to 0, to calculate the sum of the subarray starting at index i.
    • The inner loop, controlled by variable j, goes from i to n-1. In each iteration of this loop, add the value nums[j] to s. This effectively extends the subarray by one element in each iteration.
    • After adding nums[j] to s, append the new sum to arr.
  3. Once all sums are calculated, sort the list arr with the .sort() method. This arranges all the subarray sums in non-decreasing order.

  4. Calculate the sum of the elements from index left-1 to right-1 in the sorted list arr. This is done with the slice notation arr[left - 1 : right].

  5. Compute the result modulo 10**9 + 7 to get the output within the specified range and handle any potential integer overflow. This is important since the sum of subarray sums could be very large.

  6. Return the result.

In summary, the approach uses:

  • Brute force algorithm: to generate all subarray sums.
  • Sorting: to arrange the sums in non-decreasing order.
  • Prefix sum technique: by maintaining a running sum s as we iterate through the array.
  • Modular arithmetic: to ensure the final sum stays within the specified limits.

The time complexity of this approach is O(n^2) for generating the subarray sums and O((n*(n+1)/2) * log(n*(n+1)/2)) for sorting, where n is the length of the nums array. The space complexity is O(n*(n+1)/2) since we are storing the sum of each possible subarray in arr.

💪
Level Up Your
Algo Skills

Example Walkthrough

To illustrate the solution approach, let's consider a small example:

Suppose we have an array nums = [1, 2, 3], with left = 2 and right = 3. We need to find the sum of the sorted subarray sums from the left to right indices, inclusive.

  1. Initialize arr: We start with an empty list arr to hold the sums of all non-empty continuous subarrays.

  2. Iterate using nested loops:

    • The outer loop runs with i from 0 to 2 (the length of nums minus one).
    • The inner loop starts with j at i, with s initialized to 0 each time the outer loop starts.

Iteration breakdown:

  • For i = 0:

    • j = 0 : s = 0 + nums[0] (add 1), arr becomes [1].
    • j = 1 : s = 1 + nums[1] (add 2), arr becomes [1, 3].
    • j = 2 : s = 3 + nums[2] (add 3), arr becomes [1, 3, 6].
  • For i = 1:

    • j = 1 : s = 0 + nums[1] (add 2), arr becomes [1, 3, 6, 2].
    • j = 2 : s = 2 + nums[2] (add 3), arr becomes [1, 3, 6, 2, 5].
  • For i = 2:

    • j = 2 : s = 0 + nums[2] (add 3), arr becomes [1, 3, 6, 2, 5, 3].
  1. Sorting arr: We sort arr, resulting in [1, 2, 3, 3, 5, 6].

  2. Calculate the result: We sum the elements from left-1 to right-1, which corresponds to the second (index 1) and third (index 2) elements in the sorted arr. This gives us the sum of 2 + 3 = 5.

  3. Modular arithmetic: The final step is to take the result modulo 10**9 + 7. Since 5 is already less than 10**9 + 7, the answer remains 5.

The method returns the result 5, which is the sum of the second and third smallest sums of non-empty continuous subarrays of nums. In this case, the sums of these subarrays are 2 for the subarray [2] and 3 for the subarrays [3] and [1, 2]. Since [3] appears twice, we only count it once in the specified range.

This walkthrough summarizes the steps in the provided solution to compute the sum of subarray sums in a given range after sorting them, thereby displaying the complete process from initialization through to obtaining the final result.

Python Solution

1from typing import List
2
3class Solution:
4    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
5        # Initialize an array to store the sum of contiguous subarrays
6        subarray_sums = []
7      
8        # Calculate the sum of every contiguous subarray and store it into subarray_sums
9        for i in range(n):
10            current_sum = 0
11            for j in range(i, n):
12                current_sum += nums[j]  # Add the current element to the sum
13                subarray_sums.append(current_sum)  # Append the current sum to the list
14      
15        # Sort the array of subarray sums in non-decreasing order
16        subarray_sums.sort()
17      
18        # Define the modulus value to prevent integer overflow issues
19        mod = 10**9 + 7
20      
21        # Compute the sum of the elements from the 'left' to 'right' indices
22        # Note: The '-1' adjustment is required because list indices in Python are 0-based
23        range_sum = sum(subarray_sums[left - 1 : right]) % mod
24      
25        # Return the computed sum modulo 10^9 + 7
26        return range_sum
27

Java Solution

1import java.util.Arrays; // Import Arrays class for sorting
2
3class Solution {
4  
5    // This method calculates the sum of values within a given range of subarray sums from nums array
6    public int rangeSum(int[] nums, int n, int left, int right) {
7        // Calculate the total number of subarray sums
8        int totalSubarrays = n * (n + 1) / 2;
9        // Initialize an array to store all possible subarray sums
10        int[] subarraySums = new int[totalSubarrays];
11      
12        int index = 0; // Index to insert the next sum into subarraySums
13        // Loop over nums array to define starting point of subarray
14        for (int i = 0; i < n; ++i) {
15            int currentSum = 0; // Holds the temporary sum of the current subarray
16            // Loop over nums array to create subarrays starting at index i
17            for (int j = i; j < n; ++j) {
18                currentSum += nums[j]; // Add the current number to the current subarray sum
19                subarraySums[index++] = currentSum; // Store the current subarray sum and increment index
20            }
21        }
22      
23        // Sort the array of subarray sums
24        Arrays.sort(subarraySums);
25      
26        int result = 0; // Initialize the result to 0
27        final int mod = (int) 1e9 + 7; // Modulo value to prevent integer overflow
28        // Add the values from position "left" to "right" in the sorted subarray sums
29        for (int i = left - 1; i < right; ++i) {
30            result = (result + subarraySums[i]) % mod;
31        }
32      
33        return result; // Return the computed sum
34    }
35}
36

C++ Solution

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int rangeSum(vector<int>& nums, int n, int left, int right) {
7        // Create an array to store the sums of all subarrays, with size based on the number of possible subarrays
8        vector<int> subarraySums(n * (n + 1) / 2);
9        int k = 0; // Index for inserting into subarraySums
10      
11        // Calculate the sum of all possible subarrays
12        for (int start = 0; start < n; ++start) {
13            int currentSum = 0; // Stores the sum of the current subarray
14            for (int end = start; end < n; ++end) {
15                currentSum += nums[end]; // Add the next element to the currentSum
16                subarraySums[k++] = currentSum; // Store the sum of the subarray
17            }
18        }
19      
20        // Sort the sums of the subarrays
21        sort(subarraySums.begin(), subarraySums.end());
22      
23        int answer = 0; // Variable to store the final answer
24        const int mod = 1e9 + 7; // The modulo value
25      
26        // Calculate the sum of the subarray sums between indices left-1 and right-1 (inclusive)
27        for (int i = left - 1; i < right; ++i) {
28            answer = (answer + subarraySums[i]) % mod; // Aggregate the sum modulo mod
29        }
30      
31        return answer; // Return the final calculated sum
32    }
33};
34

Typescript Solution

1function rangeSum(nums: number[], n: number, left: number, right: number): number {
2    // Calculate the number of possible subarrays and initialize an array to store their sums
3    let subarraySums: number[] = new Array(n * (n + 1) / 2);
4    let index = 0; // Index for inserting into subarraySums
5  
6    // Calculate the sum of all possible subarrays
7    for (let start = 0; start < n; ++start) {
8        let currentSum = 0; // Stores the sum of the current subarray
9        for (let end = start; end < n; ++end) {
10            currentSum += nums[end]; // Add the next element to the current sum
11            subarraySums[index++] = currentSum; // Store the sum of the subarray
12        }
13    }
14  
15    // Sort the sums of the subarrays
16    subarraySums.sort((a, b) => a - b);
17  
18    let answer = 0; // Variable to store the final answer
19    const MOD = 1e9 + 7; // The modulo value
20  
21    // Calculate the sum of the subarray sums between indices left-1 and right-1 (inclusive)
22    for (let i = left - 1; i < right; ++i) {
23        answer = (answer + subarraySums[i]) % MOD; // Aggregate the sum modulo MOD
24    }
25  
26    return answer; // Return the final calculated sum
27}
28

Time and Space Complexity

The given Python code computes the range sum of all possible contiguous subarrays sorted in a non-decreasing order and then returns the sum of the subarray values from the left to right indices (1-indexed). Here is the complexity analysis:

  • Time Complexity:

    • The outer loop runs n times, where n is the length of the input list nums.
    • The inner loop runs n - i times for each iteration of the outer loop, summing elements and appending the sum to the array arr. When i is 0, the inner loop will run n times; when i is n-1, it will run 1 time. On average, it will run n/2 times.
    • The sort operation on the array arr of size n * (n + 1) / 2 (the total number of subarrays) has a time complexity of O(n^2 * log(n^2)) which simplifies to O(n^2 * log(n)).
    • The sum operation over arr[left - 1 : right] can be considered O(k), where k is the difference between right and left. However, this is negligible compared to the sorting complexity.

    Combining these, the overall time complexity is dominated by the sort, resulting in O(n^2 * log(n)).

  • Space Complexity:

    • The space used by the array arr, which stores the n * (n + 1) / 2 sum values, dominates the space complexity. This results in O(n^2).
    • No other significant space-consuming structures or recursive calls that would impact the overall space complexity.

Therefore, the space complexity of the code is O(n^2) and the time complexity is O(n^2 * log(n)).

😈
Become an
Algo Monster

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.


TA 👨‍🏫