Domain 2MediumMEDIUM

Range Sum of Sorted Subarray Sums

Generate all subarray sums in O(n^2), sort them, and sum the range [left-1:right] modulo 10^9+7.

Domain: medium•Updated: 2026-09-17
#subarrays#sorting#O(n^2 log n)#counting sort

Problem Breakdown

We are given an array of positive integers nums with length nn. The core task involves generating every possible non-empty continuous subarray sum from this input. There are exactly n(n+1)2\frac{n(n+1)}{2} such sums (e.g., for [1, 2], we have [1], [2], [1, 2]).

Once generated, these sums must be sorted in ascending order to form a new conceptual array. We then need to calculate the sum of elements within this sorted sequence from index left to right (inclusive), using 1-based indexing. Finally, we return the result modulo 109+710^9 + 7.

Key Inputs:

  • nums: List of positive integers (n≤103n \le 10^3).
  • left, right: Range bounds in the sorted sums array.

Implicit Constraints & Edge Cases:

  • Overflow: The sum can be large, but Python handles arbitrary precision integers automatically. We only apply modulo at the very end to ensure correctness before returning.
  • Duplicates: Subarray sums may not be unique (e.g., [1, 2] and [3]). Sorting must handle duplicates naturally (sort() does this).
  • Indexing: The problem uses 1-based indexing for left/right, so we convert to 0-based before slicing.

Intuition

A brute-force approach would be:

  1. Generate all subarray sums (O(n2)O(n^2) operations if optimized, O(n3)O(n^3) naively).
  2. Sort the resulting list of sums (O(Mlog⁡M)O(M \log M) where M=n(n+1)/2M = n(n+1)/2).
  3. Sum the required range and apply modulo.

Why Brute Force is Insufficient (Naive): If we used sum(nums[i:j]) inside a nested loop, calculating each sum takes time proportional to subarray length. This leads to an O(n3)O(n^3) complexity for generation (10910^9 operations), which would Time Limit Exceed (TLE). We must optimize the generation step using a running accumulator variable.

Optimization Insight: Since we need the sums sorted, sorting is unavoidable unless we use Counting Sort / Bucket Sort logic given that nums[i] are small (≤100\le 100) and max sum ≈105\approx 10^5. However, Python’s Timsort on integers is highly optimized. Given n=1000n=1000, the number of subarrays is roughly 5×1055 \times 10^5. Sorting this list takes acceptable time within typical interview limits (usually ~3-4 seconds for Python). I will implement the standard sort approach as it’s cleaner, but note that Counting Sort could reduce sorting complexity to linear with respect to the sum range.

Approach

  1. Generate Sums Efficiently: Use a nested loop where we maintain a current_sum variable inside the inner loop. This ensures each subarray is processed in O(1)O(1) time, keeping generation at O(n2)O(n^2). Avoid slicing and calling sum() repeatedly to prevent O(n3)O(n^3).
  2. Sort: Sort the list of generated sums using Python’s built-in sort (Timsort). This takes O(Mlog⁡M)O(M \log M) where MM is total subarrays.
  3. Query Range: Convert 1-based left and right to 0-based indices (left-1, right). Slice the sorted list from this range. Note: Python slicing [start:end] excludes end. We need inclusive, so slice up to right + 1.
  4. Calculate Result: Sum the sliced elements. Apply modulo 109+710^9 + 7 before returning.

Complexity Analysis

  • Time Complexity: O(n2log⁡n)O(n^2 \log n). Generating sums takes O(n2)O(n^2) (specifically n(n+1)2\frac{n(n+1)}{2}). Sorting takes O(Mlog⁡M)O(M \log M) where M=O(n2)M = O(n^2). Thus, sorting dominates with roughly n2⋅2log⁡nn^2 \cdot 2\log n operations. With counting sort optimization, it could be reduced to O(n2+S)O(n^2 + S) (where SS is max sum), but standard sort passes given constraints (N=1000N=1000).
  • Space Complexity: O(M)=O(n2)O(M) = O(n^2) to store the subarray sums.

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: Generate all subarray sums efficiently using a running sum variable.
        # This avoids O(n^3) complexity that would occur if we sliced and summed repeatedly.
        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)
                
        # Step 2: Sort the sums to order them non-decreasingly.
        subarray_sums.sort()
        
        # Step 3: Extract elements from index left-1 to right (inclusive).
        # Python slicing is exclusive at end, so we use right + 1? 
        # Wait, indices are 0-based in list. We want range [left, right] inclusive (1-based).
        # In 0-based this corresponds to indices: left-1 ... right-1.
        # Slice syntax [start:end] includes start, excludes end.
        # So we need slice from left-1 up to (right-1)+1 = right.
        
        range_sum = sum(subarray_sums[left - 1 : right]) % MOD
        
        return range_sum

Edge Cases Handled

  • Single Element Array: If n=1, the loop runs once for one subarray [nums[0]]. Sorting and slicing works correctly.
  • Range Boundaries (left = 1, right = total): Slicing handles full