Range Sum of Sorted Subarray Sums — Problem & Solution
Range Sum of Sorted Subarray Sums solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Range Sum of Sorted Subarray Sums is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of n positive integers. Compute the sum of every non-empty contiguous subarray — there are n * (n + 1) / 2 of them — and sort those sums in non-decreasing order, giving a new array (1-indexed).
Return the sum of the elements of that new array from position left to position right, both included. Since it can be large, return it modulo 10^9 + 7.
Example 1
Input: nums = [2,1,3], n = 3, left = 2, right = 5
Output: 12
Explanation: The subarray sums are 2, 3, 6, 1, 4, 3; sorted: [1,2,3,3,4,6]. Positions 2 to 5 add up to 2 + 3 + 3 + 4 = 12.
Example 2
Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Example 3
Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50
Constraints
n == nums.length1 <= nums.length <= 10001 <= nums[i] <= 1001 <= left <= right <= n * (n + 1) / 2
Hints for Range Sum of Sorted Subarray Sums
Hint 1
There are at most about 500,000 subarray sums — few enough to list.
Hint 2
Generate them with a running sum from each start index, sort, and add up the requested slice.
Hint 3
For larger inputs, binary-search the value of the
k-th smallest sum and count sums below it with two pointers; the answer isF(right) - F(left - 1)whereF(k)is the sum of theksmallest.
How to solve Range Sum of Sorted Subarray Sums
With n <= 1000 the full list of subarray sums has at most 500500 entries, so materialising and sorting it is fast. (A min-heap merging the n increasing rows, or a binary search on the value, avoid the full list when memory matters.)
Approach
- For each start
i, extendjfromiton - 1keeping a running sum, and record every sum. - Sort the sums ascending.
- Add the sums at positions
left - 1throughright - 1(0-based) in 64-bit arithmetic and return the result modulo10^9 + 7.
Why it works
The sorted list is exactly the array the statement describes, so the slice sum is the answer by definition; reducing modulo 10^9 + 7 at the end is valid because the true total (at most about 5 * 10^10) fits comfortably in 64 bits.
Complexity
- Time —
O(n^2 log n) - Space —
O(n^2)
Pitfalls
leftandrightare 1-indexed.- The total can exceed 32 bits before the modulo — accumulate in 64-bit.
- Only non-empty subarrays count; there are
n * (n + 1) / 2, notn^2.
Reference solution
Python
from typing import List
def rangeSum(nums: List[int], n: int, left: int, right: int) -> int:
sums = []
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
sums.append(s)
sums.sort()
return sum(sums[left - 1:right]) % 1000000007Java
public static int rangeSum(int[] nums, int n, int left, int right) {
int[] sums = new int[n * (n + 1) / 2];
int at = 0;
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = i; j < n; j++) {
s += nums[j];
sums[at++] = s;
}
}
Arrays.sort(sums);
long total = 0;
for (int k = left - 1; k < right; k++) total += sums[k];
return (int) (total % 1000000007L);
}C++
int rangeSum(vector<int>& nums, int n, int left, int right) {
vector<int> sums;
sums.reserve(n * (n + 1) / 2);
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = i; j < n; j++) {
s += nums[j];
sums.push_back(s);
}
}
sort(sums.begin(), sums.end());
long long total = 0;
for (int k = left - 1; k < right; k++) total += sums[k];
return (int) (total % 1000000007LL);
}JavaScript
var rangeSum = function(nums, n, left, right) {
var sums = [];
for (var i = 0; i < n; i++) {
var s = 0;
for (var j = i; j < n; j++) {
s += nums[j];
sums.push(s);
}
}
sums.sort(function(a, b) { return a - b; });
var total = 0; // at most about 5e10: exact in a double
for (var k = left - 1; k < right; k++) total += sums[k];
return total % 1000000007;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms