1508. Range Sum of Sorted Subarray Sums

[mah-shamim]

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

Hint:

1. Compute all sums and save it in array.
2. Then just go from LEFT to RIGHT index and calculate answer modulo 1e9 + 7.

[mah-shamim]

To solve this problem, we can follow these steps:

1. Generate all possible sums of non-empty continuous subarrays.
2. Sort the resulting array of sums.
3. Calculate the sum of the elements from the left index to the right index (1-based).
4. Return the result modulo 109 + 7.

Let's implement this solution in PHP: 1508. Range Sum of Sorted Subarray Sums

<?php

function rangeSum($nums, $n, $left, $right) {
    $MOD = 1000000007;
    $sums = array();

    // Generate all subarray sums
    for ($i = 0; $i < $n; $i++) {
        $current_sum = 0;
        for ($j = $i; $j < $n; $j++) {
            $current_sum += $nums[$j];
            $sums[] = $current_sum;
        }
    }

    // Sort the sums array
    sort($sums);

    // Calculate the sum of the elements from left to right (1-based index)
    $total = 0;
    for ($i = $left - 1; $i <= $right - 1; $i++) {
        $total = ($total + $sums[$i]) % $MOD;
    }

    return $total;
}

// Example usage
$nums = array(1, 2, 3, 4);
$n = 4;
$left = 1;
$right = 5;

echo rangeSum($nums, $n, $left, $right); // Output: 13

$left = 3;
$right = 4;
echo rangeSum($nums, $n, $left, $right); // Output: 6

$left = 1;
$right = 10;
echo rangeSum($nums, $n, $left, $right); // Output: 50

?>

Explanation:

1. Generating Subarray Sums:

   • Iterate through each starting index i of the subarray.
   • For each starting index i, compute the sum of subarrays ending at index j (where j >= i).
   • Append each computed subarray sum to the $sums array.

2. Sorting the Sums:

   • Use PHP's sort() function to sort the $sums array in non-decreasing order.

3. Summing the Required Range:

   • Iterate from the left-1 index to the right-1 index (since the problem uses 1-based indexing).
   • Accumulate the sum of the elements in this range, taking care to use modulo 109 + 7 to avoid overflow.

This solution efficiently generates all subarray sums, sorts them, and computes the required range sum as specified.