Coding Interview PatternsRange Sum of Sorted Subarray Sums
MediumK-way Merge

Range Sum of Sorted Subarray Sums

Explanation & Solution

Practice Problem

Description

You are given an integer array nums of length n. Compute all non-empty subarray sums, sort them in ascending order, and return the sum of elements from index left to right (1-indexed) in this sorted list, modulo 10^9 + 7.

Input:nums = [1,2,3,4], n = 4, left = 1, right = 5
0
1
1
2
2
3
3
4

Output: 13

Explanation: All subarray sums sorted: [1,2,3,3,4,5,6,7,9,10]. Sum of first 5 = 1+2+3+3+4 = 13.

Constraints

  • n == nums.length
  • 1 <= nums.length <= 1000
  • 1 <= left <= right <= n * (n + 1) / 2
  • -10^5 <= nums[i] <= 10^5

Approach

K-way Merge pattern

1. Enumerate All Subarray Sums

  • Use two nested loops: outer loop fixes the start index i, inner loop extends to end index j
  • Accumulate a running sum as j moves right — this avoids recomputing prefix sums from scratch
  • Push each subarray sum into the sums array

2. Sort the Sums

  • Sort sums in ascending order
  • There are n*(n+1)/2 subarray sums total

3. Sum the Target Range

  • Iterate from index left - 1 to right - 1 (convert 1-indexed to 0-indexed)
  • Accumulate the sum modulo 10^9 + 7 to prevent integer overflow

Key Insight

  • A k-way merge with a min-heap can solve this in O(n² log n) without fully materializing all sums, but for n ≤ 1000 the brute-force approach is practical and simpler
Time
O(n² log n)O(n²) to generate sums, O(n² log n) to sort
Space
O(n²) for the sums array

Visualization

Input:
[1, 2, 3, 4], n = 4
10213243
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Kth Smallest Prime Fraction
Next
Swim in Rising Water