#1508

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Range Sum of Sorted Subarray Sums

Compute the sum of sorted subarray sums efficiently using binary search over valid sum ranges and prefix sum accumulation.

array two pointers binary search sorting prefix sum

Problem Statement

Given an array nums of n positive integers, generate all non-empty continuous subarray sums and sort them in non-decreasing order to form a new array. You are asked to compute efficiently without explicitly storing all sums for large n.

Return the sum of elements from index left to index right (1-based) in the sorted subarray sums array, modulo 10^9 + 7. For example, given nums = [1,2,3,4], left = 1, and right = 5, the answer is 13.

Examples

Example 1

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

Output: 13

All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

Example 2

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

Output: 6

The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3

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

Output: 50

Example details omitted.

Constraints

n == nums.length
1 <= nums.length <= 1000
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

Solution Approach

Use Prefix Sums to Compute Subarray Sums Quickly

Precompute prefix sums of nums to allow O(1) computation of any subarray sum. This avoids recomputing sums repeatedly and enables counting subarray sums in the binary search step efficiently.

Binary Search Over Possible Subarray Sum Values

Define a range from minimum to maximum possible subarray sum. For each candidate mid value, count how many subarray sums are less than or equal to mid using prefix sums. This identifies the range of sums that correspond to the left and right indices efficiently without full sorting.

Accumulate Sums Within Target Indices

After locating the sums corresponding to left and right indices via binary search, calculate the total sum by iterating over subarrays and adding sums that fall within the target count. Apply modulo 10^9 + 7 at each step to handle large numbers.

Complexity Analysis

Metric	Value
Time	O(n \log sum)
Space	O(1)

Time complexity is O(n log sum) because each binary search step counts subarray sums in O(n) and the range of sums is at most sum(nums). Space complexity is O(1) aside from storing prefix sums.

What Interviewers Usually Probe

Expect a solution that avoids generating all subarray sums explicitly.
Look for prefix sum optimization before binary search.
Check if the candidate correctly counts sums within the desired range.

Common Pitfalls or Variants

Common pitfalls

Trying to sort all subarray sums directly leads to TLE for n = 1000.
Incorrectly calculating indices in 1-based versus 0-based arrays.
Overflowing sum if modulo 10^9 + 7 is not applied incrementally.

Follow-up variants

Compute only the k-th smallest subarray sum using the same binary search pattern.
Return multiple disjoint ranges of sorted subarray sums efficiently.
Adapt the solution to allow negative numbers with modified counting in binary search.

FAQ

How do I handle large arrays without generating all subarray sums?

Use prefix sums and binary search over possible sum values to count subarrays within the target range instead of full sorting.

Why is binary search over sum space preferred here?

It allows efficiently locating the subarray sums that correspond to the left and right indices without generating the entire sorted array.

Do I need to sort the subarray sums explicitly?

No, counting sums via prefix sums in binary search eliminates the need for full sorting, saving time and space.

How should I apply modulo 10^9 + 7 in this problem?

Accumulate the sum incrementally while applying modulo 10^9 + 7 to avoid integer overflow.

What pattern does this problem follow?

It follows the 'Binary search over the valid answer space' pattern combined with prefix sums for efficient subarray sum counting.

terminal

Solution

Solution 1: Simulation

We can generate the array $\textit{arr}$ according to the problem's requirements, then sort the array, and finally calculate the sum of all elements in the range $[\textit{left}-1, \textit{right}-1]$ to get the result.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        arr = []
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                arr.append(s)
        arr.sort()
        mod = 10**9 + 7
        return sum(arr[left - 1 : right]) % mod

Continue Practicing

#2234 maximum total beauty of the gardens #1498 number of subsequences that satisfy the given sum condition #1346 check if n and its double exist