{x}
blog image

Range Sum of Sorted Subarray Sums

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 109 + 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.

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

 

Constraints:

  • n == nums.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

Solution Explanation: Range Sum of Sorted Subarray Sums

This problem requires calculating the sum of subarray sums within a specified range after sorting them. The solution involves several steps:

1. Generating Subarray Sums:

The first step is to generate all possible non-empty continuous subarray sums from the input array nums. This is done using nested loops. The outer loop iterates through each element as a starting point, and the inner loop iterates through all subsequent elements to form subarrays. The sum of each subarray is calculated and stored.

2. Sorting Subarray Sums:

The generated subarray sums are then sorted in non-decreasing order. This step is crucial to ensure that the sum is calculated from the correct indices in the specified range.

3. Calculating the Range Sum:

Finally, the sum of the subarray sums from index left to right (inclusive, but 1-indexed, so adjust indices accordingly in the code) is calculated. To handle potentially large sums, the modulo operator (%) with 10<sup>9</sup> + 7 is used to prevent integer overflow.

Time Complexity Analysis:

  • Generating Subarray Sums: The nested loops have a time complexity of O(n2), where n is the length of the input array nums.
  • Sorting: Sorting the array of subarray sums takes O(n2 log n) time using efficient algorithms like merge sort or quicksort.
  • Calculating Range Sum: The final summation has a time complexity of O(n2).

Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n2 log n).

Space Complexity Analysis:

The space complexity is determined by the array used to store the subarray sums. This array has a size proportional to the number of subarrays, which is O(n2). Therefore, the space complexity is O(n2).

Code Examples (Python):

The Python code efficiently implements the solution:

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        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)
 
        subarray_sums.sort()  # Sort the subarray sums
        total_sum = 0
        mod = 10**9 + 7
        for i in range(left - 1, right): # Adjust indices for 1-based indexing
            total_sum = (total_sum + subarray_sums[i]) % mod
 
        return total_sum

This code directly reflects the three steps described above: generation of subarray sums, sorting, and calculating the range sum with modulo arithmetic to prevent overflow. Other languages would follow a very similar structure.