Watch 10 video solutions for Range Sum of Sorted Subarray Sums, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCodeIO has 15,550 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5 Output: 13 Explanation: 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 Explanation: 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
Constraints:
n == nums.length1 <= nums.length <= 10001 <= nums[i] <= 1001 <= left <= right <= n * (n + 1) / 2Problem Overview: You are given an array nums. Generate the sum of every possible subarray, sort those sums, then return the total of elements from index left to right (1-indexed) in the sorted list. The challenge is handling up to n(n+1)/2 subarray sums efficiently.
Approach 1: Brute Force with Sorting (O(n² log n) time, O(n²) space)
Generate every possible subarray sum using two nested loops. Start an index i, extend the subarray with j, and keep a running sum to avoid recomputing values. Store each subarray sum in a list. After generating all sums, sort the list and add the values between left and right. This approach is straightforward and easy to implement using basic array traversal and sorting. The drawback is memory usage because the algorithm explicitly stores up to O(n²) sums.
Approach 2: Min-Heap for Efficient Range (O((n + right) log n) time, O(n) space)
Instead of generating all subarray sums, treat each starting index as a sorted stream of increasing sums. Push the first subarray sum starting at every index into a min-heap. Each heap entry stores the current sum and the next index to extend. Repeatedly pop the smallest sum from the heap, which produces the next element in the globally sorted sequence of subarray sums. If the popped subarray can be extended, push the new sum back into the heap. Continue until reaching the rightth element and accumulate results only between left and right. This technique works because subarray sums grow as you extend the end pointer, which forms naturally sorted sequences. The heap efficiently merges these sequences, similar to a k-way merge in sorting problems. Concepts from two pointers appear when extending subarrays incrementally.
Recommended for interviews: Start with the brute force explanation to show you understand how subarray sums are formed. Then move to the min-heap optimization, which avoids storing all O(n²) sums and generates them in sorted order on demand. Interviewers typically expect the heap-based approach because it demonstrates knowledge of priority queues and efficient sequence merging.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Sorting | O(n² log n) | O(n²) | Good for understanding the problem and when n is small |
| Min-Heap Incremental Generation | O((n + right) log n) | O(n) | Preferred when you only need a portion of the sorted sums and want better memory efficiency |