Problem Description

Given an integer array nums of length n, you are to consider all possible non-empty contiguous subarrays of nums. For each subarray, compute its sum. Collect all these subarray sums into an array, then sort this array in non-decreasing order.

Given two integers left and right, return the sum of the elements from index left to right (1-indexed) in the sorted array of subarray sums. Since the answer may be large, return it modulo 10^9 + 7.

• Each subarray sum must come from a contiguous subarray (no skipping elements).
• All subarray sums are collected, sorted, and then the sum of the subarray sums from left to right (inclusive, 1-based) is returned.
• Constraints: 1 <= nums.length <= 1000, 1 <= nums[i] <= 100, 1 <= left <= right <= n * (n + 1) / 2.

Thought Process

At first glance, the problem asks us to consider all possible contiguous subarrays, compute their sums, sort these sums, and then return the sum of a particular range. The naive approach would be to generate every subarray, compute its sum, sort the results, and sum the desired range. This is straightforward, but with up to n * (n + 1) / 2 subarrays (about 500,000 when n = 1000), we must be careful with performance.

The key insight is that while the number of subarrays is large, it is manageable for modern hardware if we avoid repeated computation. Instead of recalculating sums for overlapping subarrays, we can use prefix sums to compute each subarray sum in constant time. Sorting and summing a range is then a direct operation.

Solution Approach

• Step 1: Compute Prefix Sums
  • Create a prefix sum array so that the sum of any subarray nums[i:j] can be computed as prefix[j] - prefix[i].
• Step 2: Enumerate All Subarray Sums
  • Use two nested loops: for each possible starting index i, and for each ending index j (where j >= i), compute the subarray sum using the prefix sums and collect it in a list.
• Step 3: Sort the Subarray Sums
  • Sort the list of all subarray sums in non-decreasing order.
• Step 4: Compute the Desired Range Sum
  • Sum the elements from left-1 to right-1 (since the problem uses 1-based indexing) in the sorted array of subarray sums.
• Step 5: Return Result Modulo 1e9+7
  • As required, return the result modulo 10^9 + 7 to avoid overflow.

This approach is efficient for n <= 1000 and avoids unnecessary recomputation.

Example Walkthrough

Let's use nums = [1, 2, 3, 4], left = 3, right = 4.

1. Compute all subarray sums:
   • Subarrays: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], [1,2,3,4]
   • Sums: 1, 2, 3, 4, 3, 5, 7, 6, 9, 10
2. Sort the sums:
   • Sorted: 1, 2, 3, 3, 4, 5, 6, 7, 9, 10
3. Sum from index 3 to 4 (1-based):
   • Elements: 3 (index 2), 3 (index 3)
   • Sum: 3 + 3 = 6
4. Return 6.

Time and Space Complexity

• Brute-force approach:
  • For each subarray, sum elements directly: O(n^3) time (nested loops and sum for each subarray).
• Optimized approach (using prefix sums):
  • Prefix sum calculation: O(n)
  • Subarray sum enumeration: O(n^2) (since there are O(n^2) subarrays)
  • Sorting: O(n^2 log n^2) = O(n^2 log n)
  • Total: O(n^2 log n)
  • Space: O(n^2) for storing all subarray sums
• Why? Because there are O(n^2) subarrays, and sorting dominates the runtime.

Summary

The problem asks us to efficiently compute and process all contiguous subarray sums of an array. By leveraging prefix sums, we can avoid redundant calculations and generate all subarray sums in O(n^2) time. Sorting and summing the desired range is straightforward. The solution is both simple and effective for the given constraints, demonstrating how classic techniques like prefix sums and sorting can be combined to solve array problems efficiently.

Code Implementation

class Solution:
    def rangeSum(self, nums, n, left, right):
        MOD = 10 ** 9 + 7
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        sub_sums = []
        for i in range(n):
            for j in range(i+1, n+1):
                sub_sums.append(prefix[j] - prefix[i])
        sub_sums.sort()
        return sum(sub_sums[left-1:right]) % MOD
      

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        const int MOD = 1e9 + 7;
        vector<int> prefix(n+1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i+1] = prefix[i] + nums[i];
        }
        vector<int> sub_sums;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j <= n; ++j) {
                sub_sums.push_back(prefix[j] - prefix[i]);
            }
        }
        sort(sub_sums.begin(), sub_sums.end());
        long long res = 0;
        for (int i = left-1; i < right; ++i) {
            res = (res + sub_sums[i]) % MOD;
        }
        return (int)res;
    }
};
      

class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        int MOD = 1000000007;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; i++) {
            prefix[i+1] = prefix[i] + nums[i];
        }
        List<Integer> subSums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j <= n; j++) {
                subSums.add(prefix[j] - prefix[i]);
            }
        }
        Collections.sort(subSums);
        long res = 0;
        for (int i = left-1; i < right; i++) {
            res = (res + subSums.get(i)) % MOD;
        }
        return (int)res;
    }
}
      

var rangeSum = function(nums, n, left, right) {
    const MOD = 1e9 + 7;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        prefix[i+1] = prefix[i] + nums[i];
    }
    const subSums = [];
    for (let i = 0; i < n; ++i) {
        for (let j = i+1; j <= n; ++j) {
            subSums.push(prefix[j] - prefix[i]);
        }
    }
    subSums.sort((a, b) => a - b);
    let res = 0;
    for (let i = left-1; i < right; ++i) {
        res = (res + subSums[i]) % MOD;
    }
    return res;
};