LeetCode 1508 - Range Sum of Sorted Subarray Sums

The problem requires calculating the sum of a subrange of all possible contiguous subarray sums of a given array nums.

leetcodemediumarraytwo-pointersbinary-searchsortingprefix-sum

LeetCode Problem 1508

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting, Prefix Sum

Solution

Problem Understanding

The problem requires calculating the sum of a subrange of all possible contiguous subarray sums of a given array nums. The first step is to generate every possible continuous subarray sum, sort them in non-decreasing order, and then extract the sum of elements between the left and right indices, inclusive, with 1-based indexing. The result must be returned modulo 10^9 + 7 to prevent integer overflow.

The input nums contains n positive integers, and its length can be up to 1000. This means the total number of subarrays can be as large as n * (n + 1) / 2 = 500,500 in the worst case. The left and right parameters indicate the subrange of the sorted subarray sums that we need to sum. The key constraint is that nums[i] is guaranteed to be positive, so every subarray sum is also positive.

Edge cases include very small arrays (length 1), left and right being equal (requiring only one sum), and the maximum possible size arrays where n = 1000. These constraints imply that a naive approach that explicitly generates all subarrays and sorts them might be too slow.

Approaches

The brute-force approach is straightforward. We iterate over every possible starting index of a subarray, then iterate over every possible ending index to compute the sum. After collecting all sums, we sort them and sum the elements between left and right. This works correctly but has a time complexity of O(n^3) if implemented naively for sum computation, or O(n^2 log n^2) if prefix sums are used to reduce sum computation.

The optimal approach leverages prefix sums to calculate subarray sums in constant time, then uses a list to store all subarray sums, sorts it, and sums the required range. While this still requires generating all sums, using prefix sums reduces the inner loop complexity to O(1), giving O(n^2) time for subarray sum generation and O(n^2 log n^2) for sorting. Given n <= 1000, this is feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n^2) Compute sums for all subarrays without prefix sums
Optimal O(n^2 log n) O(n^2) Use prefix sums to compute subarray sums efficiently, then sort

Algorithm Walkthrough

  1. Compute the prefix sum array prefix such that prefix[i] contains the sum of the first i elements. This allows computing the sum of any subarray nums[i:j] in constant time as prefix[j+1] - prefix[i].
  2. Initialize an empty list subarray_sums.
  3. Iterate over all possible starting indices i of the array. For each i, iterate over all ending indices j >= i.
  4. For each pair (i, j), calculate the subarray sum using prefix[j+1] - prefix[i] and append it to subarray_sums.
  5. Sort subarray_sums in non-decreasing order.
  6. Sum the elements from left-1 to right-1 in the sorted list, applying modulo 10^9 + 7.
  7. Return the resulting sum.

Why it works: Using prefix sums guarantees O(1) computation for any subarray sum. Sorting ensures that the subarray sums are ordered correctly, so taking the sum between left and right indices produces the correct output.

Python Solution

from typing import List

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MOD = 10**9 + 7
        
        # Step 1: Compute prefix sums
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        # Step 2: Generate all subarray sums using prefix sums
        subarray_sums = []
        for i in range(n):
            for j in range(i, n):
                subarray_sums.append(prefix[j + 1] - prefix[i])
        
        # Step 3: Sort subarray sums
        subarray_sums.sort()
        
        # Step 4: Sum the requested range
        result = sum(subarray_sums[left-1:right]) % MOD
        
        return result

The Python implementation first builds the prefix sum array, which allows fast subarray sum computation. It then generates all subarray sums, sorts them, and calculates the sum in the requested range with modulo operation to handle large sums.

Go Solution

package main

func rangeSum(nums []int, n int, left int, right int) int {
    const MOD = 1_000_000_007
    
    // Step 1: Compute prefix sums
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + nums[i]
    }
    
    // Step 2: Generate all subarray sums
    subarraySums := make([]int, 0, n*(n+1)/2)
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            subarraySums = append(subarraySums, prefix[j+1]-prefix[i])
        }
    }
    
    // Step 3: Sort subarray sums
    sort.Ints(subarraySums)
    
    // Step 4: Sum the requested range
    result := 0
    for i := left - 1; i < right; i++ {
        result = (result + subarraySums[i]) % MOD
    }
    
    return result
}

In Go, the approach mirrors Python. Slices are used to store prefix sums and subarray sums. The modulo operation ensures we avoid integer overflow. sort.Ints handles the sorting efficiently.

Worked Examples

Example 1: nums = [1,2,3,4], left = 1, right = 5

i j prefix[j+1]-prefix[i]
0 0 1
0 1 3
0 2 6
0 3 10
1 1 2
1 2 5
1 3 9
2 2 3
2 3 7
3 3 4

Sorted: [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]

Sum indices 1-5: 1 + 2 + 3 + 3 + 4 = 13

Example 2: nums = [1,2,3,4], left = 3, right = 4

Sum of indices 3-4: 3 + 3 = 6

Example 3: nums = [1,2,3,4], left = 1, right = 10

Sum of all: 50

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 log n) Generating subarray sums O(n^2) and sorting O(n^2 log n) dominates
Space O(n^2) Storing all subarray sums

The algorithm scales quadratically with n, which is feasible given n <= 1000.

Test Cases

# Provided examples
assert Solution().rangeSum([1,2,3,4], 4, 1, 5) == 13
assert Solution().rangeSum([1,2,3,4], 4, 3, 4) == 6
assert Solution().rangeSum([1,2,3,4], 4, 1, 10) == 50

# Edge cases
assert Solution().rangeSum([1], 1, 1, 1) == 1  # Single element
assert Solution().rangeSum([100]*1000, 1000, 1, 500500) == (100*1000*501//2) % (10**9+7)  # Max size array
assert Solution().rangeSum([1,2], 2, 1, 3) == 6  # Small array, sum all subarrays
Test Why
Single element Edge case with minimal input
Max size array Stress test for time and modulo correctness
Small array Ensures correct computation of multiple subarray sums

Edge Cases

The first important edge case is when nums contains only one element. In this case, there is only one subarray sum, and left and right must both be 1. The algorithm handles this correctly because prefix sums and loops still compute a single sum.

The second edge case is when left equals right, meaning we only sum one element in the sorted subarray sums. This could be