Range Sum of Sorted Subarray Sums

You are given an array nums of n positive integers. Compute all possible subarray sums, sort those sums in non-decreasing order, and return the sum of the elements from index left to index right (1-indexed). Because the answer can be large, return it modulo 10^9 + 7.

This is LeetCode 1508: Range Sum of Sorted Subarray Sums, a medium problem that blends enumeration, sorting, and modular arithmetic. The core challenge is understanding how many subarray sums exist and computing them efficiently.

Why this problem matters

Range Sum of Sorted Subarray Sums exercises a few skills that come up repeatedly in interviews. First, you need to enumerate all subarrays of an array, which is a fundamental technique for brute-force baselines. Second, you need to sort a derived dataset and work with a specific range of it. Third, you need to apply modular arithmetic to avoid integer overflow.

The problem also serves as a stepping stone toward more advanced subarray-sum problems. Once you are comfortable generating and manipulating all subarray sums, problems like Subarray Sum Equals K and sliding window variants feel much more approachable.

The key insight

The total number of subarrays in an array of length n is n * (n + 1) / 2. For each starting index i, you can extend the subarray to every ending index j where j >= i. If you accumulate the running sum as you extend, you generate all subarray sums in O(n^2) time.

Once you have the flat list of sums, sort it. Then slice out the elements from index left - 1 to right - 1 (converting from 1-indexed to 0-indexed), sum them up, and take the result modulo 10^9 + 7.

There is no clever trick needed here. The problem is designed so that n is at most 1000, which means the number of subarray sums is at most 500,500. That fits comfortably in memory and sorts quickly.

The solution

def rangeSum(nums, n, left, right):
    MOD = 10**9 + 7
    sums = []
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            sums.append(total)
    sums.sort()
    result = 0
    for k in range(left - 1, right):
        result = (result + sums[k]) % MOD
    return result

Let's walk through each piece:

1. Generate all subarray sums. The outer loop fixes the starting index i. The inner loop extends the subarray one element at a time, accumulating total. Each time we extend, we append the current total to the sums list. This avoids recomputing sums from scratch for every pair (i, j).

2. Sort the sums. A simple sort puts the subarray sums in non-decreasing order. With at most 500,500 elements, this is fast.

3. Sum the range. Loop from left - 1 to right - 1 (0-indexed), adding each element to result. Apply the modulo at each step to prevent overflow.

4. Return the result. The final value of result is already reduced modulo 10^9 + 7.

Visual walkthrough

Let's trace through nums = [1, 2, 3, 4] with n = 4, left = 2, right = 5 step by step.

The answer is 12. We generated 10 subarray sums, sorted them into [1, 2, 3, 3, 4, 5, 6, 7, 9, 10], then summed positions 2 through 5 (1-indexed): 2 + 3 + 3 + 4 = 12.

Complexity analysis

The summing step is O(right - left + 1), which is at most O(n^2), so it does not dominate. With n up to 1000, this means up to about 500,000 elements to sort. That is well within time limits.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Subarray enumeration with running sums

The pattern of iterating over all subarrays using a nested loop with an accumulator:

for i in range(n):
    total = 0
    for j in range(i, n):
        total += nums[j]
        process(total)

This avoids recomputing each subarray sum from scratch (which would be O(n^3)). By maintaining a running total as you extend the right boundary, you get all n * (n + 1) / 2 subarray sums in O(n^2) time. The same enumeration pattern appears in Subarray Sum Equals K and Maximum Subarray, where you need to examine every contiguous slice of the array.

2. Sort-then-query

The pattern of sorting a derived dataset and then answering range queries on it:

derived = compute_all_values(data)
derived.sort()
answer = aggregate(derived[left:right])

Once the data is sorted, positional queries become trivial. You just slice and reduce. This pattern shows up in problems involving medians, percentiles, and order statistics. The sorting step is often the bottleneck, so checking whether the constraints allow O(n^2 log n) is important.

Edge cases

Before submitting, make sure your solution handles these:

• Single element array nums = [5], left = 1, right = 1: only one subarray sum (5). Answer is 5.
• left equals right: you are summing a single element of the sorted array. The logic still works without a special case.
• All elements the same nums = [3, 3, 3]: subarray sums are [3, 6, 9, 3, 6, 3], sorted to [3, 3, 3, 6, 6, 9]. Duplicates in the sorted list are fine.
• Large sums requiring modulo: when n = 1000 and elements are up to 100, individual subarray sums can reach 100,000. Summing 500,000 of them can overflow 32-bit integers. The modulo operation at each step prevents this.
• left = 1 and right = n(n+1)/2*: summing the entire sorted array. This is valid and should return the sum of all subarray sums modulo 10^9 + 7.
• Two-element array nums = [a, b]: three subarray sums (a, a+b, b). Quick to verify by hand.

From understanding to recall

You have just walked through the generate-sort-sum approach, and it makes sense. Enumerate all subarray sums with a nested loop, sort them, slice out the range, and apply the modulo. Clean and direct.

But in an interview, the pressure makes it easy to fumble the details. Do you convert from 1-indexed to 0-indexed with left - 1 or left? Do you apply the modulo inside the loop or only at the end? Do you initialize total inside the outer loop or before it? These small decisions matter, and getting one wrong means a buggy solution under time pressure.

Spaced repetition fixes this. You practice writing the subarray enumeration loop and the range sum from scratch at increasing intervals. After a few rounds, the nested loop with the running total is automatic. You see "all subarray sums" and the double loop flows out without hesitation.

The subarray enumeration pattern and the sort-then-query pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subarray Sum Equals K - Uses prefix sums and a hash map to count subarrays with a target sum, a more advanced take on subarray enumeration
• Maximum Subarray - Kadane's algorithm finds the maximum subarray sum in O(n), showing how to optimize beyond brute-force enumeration
• Product of Array Except Self - Another problem where you build a derived array from the original, using prefix and suffix products