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.
The brute force approach involves calculating the sum of all possible subarrays in the given array. Once all subarray sums are computed, we can sort this list of sums. Finally, sum the elements from the sorted list between the given 'left' and 'right' indices, returning the result modulo 10^9 + 7. This approach is straightforward to implement but not necessarily optimal in terms of time complexity.
This implementation computes all possible subarray sums and stores them in an array subarraySums. Then, it sorts this array using C's built-in qsort function. Finally, it calculates the sum of elements from index left - 1 to right - 1 in this sorted array and returns the sum modulo 10^9 + 7.
Time Complexity: O(n^2 log n) due to calculating O(n^2) subarray sums and sorting them.
Space Complexity: O(n^2), for storing subarray sums.
This approach leverages a min-heap (priority queue) data structure to efficiently find the range of the smallest elements. By pushing subarray sums into the min-heap and ensuring its size does not exceed 'right', we can directly extract the required sum by polling from the min-heap. This method avoids complete sorting and is more efficient than direct sorting for larger input sizes.
This C implementation uses a simulated min-heap by employing a binary heap data structure in an array. Subarray sums are pushed onto the heap if the heap size has not yet reached 'right', or if a sum is smaller than the maximum element on the heap, enhancing efficiency by only keeping relevant elements for subsequent calculation.
Time Complexity: O(n^2 log M), where M is the maximum heap size (i.e., 'right').
Space Complexity: O(M), since we maintain only 'M' elements in the heap.
We can generate the array arr according to the problem's requirements, then sort the array, and finally calculate the sum of all elements in the range [left-1, right-1] to get the result.
The time complexity is O(n^2 times log n), and the space complexity is O(n^2). Here, n is the length of the array given in the problem.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force with Sorting | Time Complexity: O(n^2 log n) due to calculating O(n^2) subarray sums and sorting them. |
| Using Min-Heap for Efficient Range | Time Complexity: O(n^2 log M), where M is the maximum heap size (i.e., 'right'). |
| Simulation | — |
| 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 |
Range Sum of Sorted Subarray Sums - Leetcode 1508 - Python • NeetCodeIO • 15,550 views views
Watch 9 more video solutions →Practice Range Sum of Sorted Subarray Sums with our built-in code editor and test cases.
Practice on FleetCode