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) / 2The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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'). |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,177 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