Start by recognizing that generating all subarray sums and sorting them directly is too slow for large arrays. Instead, leverage prefix sums to compute subarray sums in O(1) per subarray and apply binary search over the possible sum values to count how many subarray sums are less than a candidate. Finally, accumulate the sums falling within the target indices to get the answer modulo 10^9 + 7 efficiently.
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.
How GhostInterview Helps
- GhostInterview identifies that prefix sums plus binary search over sum space is optimal for this problem.
- It generates code templates that handle counting and sum accumulation modulo 10^9 + 7 automatically.
- The solver guides through edge cases, such as left = 1 and right = n*(n+1)/2, ensuring correctness and efficiency.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Range Sum of Sorted Subarray Sums instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Range Sum of Sorted Subarray Sums from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the maximum total beauty of gardens by strategically planting flowers using binary search over achievable flower counts.
Open problem page#1498 Number of Subsequences That Satisfy the Given Sum ConditionCount all non-empty subsequences in an integer array where the sum of the minimum and maximum elements is at most a target value efficiently.
Open problem page#1346 Check If N and Its Double ExistSolve Check If N and Its Double Exist by scanning once and checking doubles or halves in a hash set.
Open problem page