Range Sum of Sorted Subarray Sums

Medium
1437.

Range Sum of Sorted Subarray Sums

Range Sum of Sorted Subarray Sums is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

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.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} n
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeSum = function(nums, n, left, right) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

Hints for Range Sum of Sorted Subarray Sums

  1. Hint 1

    There are at most about 500,000 subarray sums — few enough to list.

  2. Hint 2

    Generate them with a running sum from each start index, sort, and add up the requested slice.

  3. 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 is F(right) - F(left - 1) where F(k) is the sum of the k smallest.

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

  1. For each start i, extend j from i to n - 1 keeping a running sum, and record every sum.
  2. Sort the sums ascending.
  3. Add the sums at positions left - 1 through right - 1 (0-based) in 64-bit arithmetic and return the result modulo 10^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

  • left and right are 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, not n^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]) % 1000000007

Java

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