Skip to main content
Talentd

Range Sum of Sorted Subarray Sums - Solution & Explanation

MediumArrayTwo PointersBinary SearchSorting20 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

Approach Overview

Problem 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 1: Brute Force with Sorting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Using Min-Heap for Efficient Range

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Simulation

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Sorting

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.

Using Min-Heap for Efficient Range

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.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with SortingO(n² log n)O(n²)Good for understanding the problem and when n is small
Min-Heap Incremental GenerationO((n + right) log n)O(n)Preferred when you only need a portion of the sorted sums and want better memory efficiency

Video Solution

Range Sum of Sorted Subarray Sums - Leetcode 1508 - Python • NeetCodeIO • 15,831 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Range Sum of Sorted Subarray Sums easy or hard?
The problem is rated Medium because generating subarray sums is simple, but optimizing beyond the brute force approach requires recognizing the heap-based sequence merging technique.
Range Sum of Sorted Subarray Sums Python/Java solution
Python implementations typically use the heapq module for the priority queue, while Java uses PriorityQueue. Both versions push the initial subarray sums and repeatedly pop and extend them until reaching the required range of sorted sums.
How to solve Range Sum of Sorted Subarray Sums in O(n)?
A strict O(n) solution is not typical for this problem because the algorithm must conceptually process many subarray sums. The best practical optimization uses a min-heap to generate only the smallest sums needed up to the right boundary, giving roughly O((n + right) log n) complexity.
What is the best approach for Range Sum of Sorted Subarray Sums?
The most practical approach uses a min-heap to generate subarray sums in sorted order without storing all O(n²) values. Each array index starts a stream of increasing sums, and a priority queue merges them. This reduces space to O(n) and runs in roughly O((n + right) log n) time.
Is Range Sum of Sorted Subarray Sums asked at Google/Amazon/Meta?
Array and heap-based problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests understanding of subarray generation, priority queues, and efficient merging of sorted sequences.
What data structure is used in Range Sum of Sorted Subarray Sums?
The optimized solution relies on a min-heap (priority queue). It stores the current smallest subarray sums and expands them incrementally, allowing the algorithm to retrieve the next smallest sum in sorted order efficiently.
What is the time complexity of Range Sum of Sorted Subarray Sums?
The brute force method generates all subarray sums and sorts them, which costs O(n² log n) time and O(n²) space. The optimized heap approach generates sums incrementally and runs in about O((n + right) log n) time with O(n) extra space.

Ready to solve this problem?

Practice Range Sum of Sorted Subarray Sums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays