Range Sum of Sorted Subarray Sums solution and explanation
Google
9 more videos on this problem
Range Sum of Sorted Subarray Sums - Leetcode 1508 - PythonNeetCodeIO · 16:13 · 15K views
Range Sum of Sorted Subarray Sums | Learning Something New | Leetcode 1508 | codestorywithMIKcodestorywithMIK · 35:31 · 13K views
Range Sum of Sorted Subarray Sums (Leetcode 1508)Coding Interviews · 16:46 · 1K views
1508. Range Sum of Sorted Subarray Sums (Leetcode Medium)Programming Live with Larry · 5:01 · 1K views
1508 Range Sum of Sorted Subarray Sums | Leetcode Daily Challenge | Java | SubArrayCakot Coding · 10:30 · 349 views
1508. Range Sum of Sorted Subarray Sums (Leetcode Badge)Algorizz · 3:05 · 195 views
8/4/24: 1508. Range Sum of Sorted Subarray SumsLeetcodeDailyGrind · 6:00 · 150 views
LeetCode 1508 - Range Sum of Sorted Subarray Sums - JavaAlpha-Code · 6:45 · 134 views
Range Sum of Sorted Subarray Sums | Leetcode 1508 | Java Code | Developer CoderDeveloper Coder · 11:29 · 99 views
1508 Range Sum of Sorted Subarray SumsMath Geeks · 1:50 · 91 views
The problem
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) / 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.
def range_sum(nums, n, left, right):
MOD = 10**9 + 7
subarray_sums = []
for i in range(n):
sum_ = 0
for j in range(i, n):
sum_ += nums[j]
subarray_sums.append(sum_)
subarray_sums.sort()
result = sum(subarray_sums[left - 1:right]) % MOD
return result
# Example usage:
nums = [1, 2, 3, 4]
print(range_sum(nums, 4, 1, 5))import java.util.*;
class Solution {
public int rangeSum(int[] nums, int n, int left, int right) {
int MOD = (int)1e9 + 7;
List<Integer> subarraySums = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
subarraySums.add(sum);
}
}
Collections.sort(subarraySums);
int result = 0;
for (int i = left - 1; i < right; i++) {
result = (result + subarraySums.get(i)) % MOD;
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
System.out.println(sol.rangeSum(nums, 4, 1, 5));
}
}#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int rangeSum(std::vector<int>& nums, int n, int left, int right) {
const int MOD = 1e9 + 7;
std::vector<int> subarraySums;
for (int i = 0; i < nums.size(); i++) {
int sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
subarraySums.push_back(sum);
}
}
std::sort(subarraySums.begin(), subarraySums.end());
int result = 0;
for (int i = left - 1; i < right; i++) {
result = (result + subarraySums[i]) % MOD;
}
return result;
}
};
int main() {
Solution sol;
std::vector<int> nums = {1, 2, 3, 4};
std::cout << sol.rangeSum(nums, 4, 1, 5) << std::endl;
return 0;
}function rangeSum(nums, n, left, right) {
const MOD = 1e9 + 7;
let subarraySums = [];
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = i; j < n; j++) {
sum += nums[j];
subarraySums.push(sum);
}
}
subarraySums.sort((a, b) => a - b);
let result = 0;
for (let i = left - 1; i < right; i++) {
result = (result + subarraySums[i]) % MOD;
}
return result;
}
// Example usage:
const nums = [1, 2, 3, 4];
console.log(rangeSum(nums, 4, 1, 5));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int rangeSum(int* nums, int numsSize, int n, int left, int right) {
int mod = 1000000007;
int totalSubarrays = n * (n + 1) / 2;
int* subarraySums = (int*)malloc(totalSubarrays * sizeof(int));
int index = 0;
for (int i = 0; i < numsSize; i++) {
int sum = 0;
for (int j = i; j < numsSize; j++) {
sum += nums[j];
subarraySums[index++] = sum;
}
}
qsort(subarraySums, totalSubarrays, sizeof(int), compare);
int result = 0;
for (int i = left - 1; i < right; i++) {
result = (result + subarraySums[i]) % mod;
}
free(subarraySums);
return result;
}
int main() {
int nums[] = {1, 2, 3, 4};
int result = rangeSum(nums, 4, 4, 1, 5);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int RangeSum(int[] nums, int n, int left, int right) {
int mod = 1000000007;
List<int> subarraySums = new List<int>();
for (int i = 0; i < nums.Length; i++) {
int sum = 0;
for (int j = i; j < nums.Length; j++) {
sum += nums[j];
subarraySums.Add(sum);
}
}
subarraySums.Sort();
int result = 0;
for (int i = left - 1; i < right; i++) {
result = (result + subarraySums[i]) % mod;
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
Console.WriteLine(sol.RangeSum(nums, 4, 1, 5));
}
}In Python, the implementation computes and collects all subarray sums into a list. This list is then sorted, making it easy to extract and compute the sum within the specified range, managing large numbers through the modulo operation.
Time Complexity: O(n^2 log n) due to sorting.
Space Complexity: O(n^2), for storing subarray sums.
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.
import heapq
def range_sum(nums, n, left, right):
MOD = 10**9 + 7
heap = []
for i in range(n):
sum_ = 0
for j in range(i, n):
sum_ += nums[j]
heapq.heappush(heap, sum_)
result = 0
for k in range(1, right + 1):
if k >= left:
result = (result + heap[0]) % MOD
heapq.heappop(heap)
return result
# Example usage
nums = [1, 2, 3, 4]
print(range_sum(nums, 4, 1, 5))import java.util.PriorityQueue;
import java.util.Comparator;
class Solution {
public int rangeSum(int[] nums, int n, int left, int right) {
final int MOD = 1_000_000_007;
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < n; i++) {
minHeap.offer(new int[]{nums[i], i});
}
int sum = 0;
for (int k = 1; k <= right; k++) {
int[] cur = minHeap.poll();
int currentSum = cur[0];
int idx = cur[1];
if (k >= left) {
sum = (sum + currentSum) % MOD;
}
if (idx + 1 < n) {
minHeap.offer(new int[]{currentSum + nums[idx + 1], idx + 1});
}
}
return sum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
System.out.println(sol.rangeSum(nums, 4, 1, 5));
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
const int MOD = 1e9 + 7;
vector<int> prefixSum(n + 1);
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
struct Compare {
bool operator()(pair<int, int>& a, pair<int, int>& b) {
return a.first > b.first;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> minHeap;
for (int i = 0; i < n; ++i) {
minHeap.push({nums[i], i});
}
int sum = 0;
for (int k = 1; k <= right; ++k) {
auto [current, idx] = minHeap.top();
minHeap.pop();
if (k >= left) {
sum = (sum + current) % MOD;
}
if (idx + 1 < n) {
minHeap.push({current + nums[idx + 1], idx + 1});
}
}
return sum;
}
};
int main() {
Solution sol;
vector<int> nums = {1, 2, 3, 4};
cout << sol.rangeSum(nums, 4, 1, 5) << endl;
return 0;
}class MinHeap {
constructor() {
this.data = [];
}
add(val) {
this.data.push(val);
this._heapifyUp();
}
remove() {
if (this.data.length < 2) return this.data.pop();
const top = this.data[0];
this.data[0] = this.data.pop();
this._heapifyDown();
return top;
}
_heapifyUp() {
let idx = this.data.length - 1;
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
if (this.data[idx] >= this.data[parentIdx]) break;
[this.data[idx], this.data[parentIdx]] = [this.data[parentIdx], this.data[idx]];
idx = parentIdx;
}
}
_heapifyDown() {
let idx = 0;
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let swapIdx = idx;
if (leftChildIdx < this.data.length && this.data[leftChildIdx] < this.data[swapIdx]) {
swapIdx = leftChildIdx;
}
if (rightChildIdx < this.data.length && this.data[rightChildIdx] < this.data[swapIdx]) {
swapIdx = rightChildIdx;
}
if (swapIdx === idx) break;
[this.data[idx], this.data[swapIdx]] = [this.data[swapIdx], this.data[idx]];
idx = swapIdx;
}
}
}
function rangeSum(nums, n, left, right) {
const MOD = 1e9 + 7;
const minHeap = new MinHeap();
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i; j < nums.length; j++) {
sum += nums[j];
minHeap.add(sum);
}
}
let currentSum = 0;
const result = [];
for (let k = 1; k <= right; k++) {
let s = minHeap.remove();
if (k >= left) result.push(s);
}
return result.reduce((a, b) => (a + b) % MOD, 0);
}
// Example usage:
const nums = [1, 2, 3, 4];
console.log(rangeSum(nums, 4, 1, 5));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct {
int row, col, sum;
} Element;
int compare(const void *a, const void *b) {
return ((Element*)a)->sum - ((Element*)b)->sum;
}
void push(Element *heap, Element *elem, int *size) {
heap[*size] = *elem;
int current = (*size)++;
while (current > 0) {
int parent = (current - 1) / 2;
if (heap[current].sum >= heap[parent].sum) break;
Element temp = heap[current];
heap[current] = heap[parent];
heap[parent] = temp;
current = parent;
}
}
Element pop(Element *heap, int *size) {
Element top = heap[0];
heap[0] = heap[--(*size)];
int current = 0;
while (current * 2 + 1 < *size) {
int child = current * 2 + 1;
if (child + 1 < *size && heap[child + 1].sum < heap[child].sum) {
child++;
}
if (heap[current].sum <= heap[child].sum) break;
Element temp = heap[current];
heap[current] = heap[child];
heap[child] = temp;
current = child;
}
return top;
}
int rangeSum(int* nums, int numsSize, int n, int left, int right) {
int mod = 1000000007;
Element heap[right];
int heapSize = 0;
for (int i = 0; i < numsSize; i++) {
int sum = 0;
for (int j = i; j < numsSize; j++) {
sum += nums[j];
if (heapSize < right) {
Element elem = {i, j, sum};
push(heap, &elem, &heapSize);
} else if (sum < heap[0].sum) {
Element elem = {i, j, sum};
pop(heap, &heapSize);
push(heap, &elem, &heapSize);
}
}
}
int result = 0;
for (int i = 0; i < heapSize; i++) {
result = (result + heap[i].sum) % mod;
}
qsort(heap, heapSize, sizeof(Element), compare);
result = 0;
for (int i = left - 1; i < heapSize; i++) {
result = (result + heap[i].sum) % mod;
}
return result;
}
int main() {
int nums[] = {1, 2, 3, 4};
printf("%d\n", rangeSum(nums, 4, 4, 1, 5));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int RangeSum(int[] nums, int n, int left, int right) {
int MOD = 1000000007;
PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
minHeap.Enqueue(sum, sum);
}
}
int result = 0;
for (int k = 1; k <= right; k++) {
int currentSum = minHeap.Dequeue();
if (k >= left) {
result = (result + currentSum) % MOD;
}
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
Console.WriteLine(sol.RangeSum(nums, 4, 1, 5));
}
}The Python solution applies the heapq module to create and manage a min-heap for subarray sums. Sums are extracted in increasing order, ensuring only those within the specified range contribute to the final summation, rendering both efficient time use and clarity.
Time Complexity: O(n^2 log right), as total subarray sums could be n^2 but managed within right for heap operations.
Space Complexity: O(right), the maintained heap reflecting only the essential elements for summation.
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.
function rangeSum(nums: number[], n: number, left: number, right: number): number {
let arr = Array((n * (n + 1)) / 2).fill(0);
const mod = 10 ** 9 + 7;
for (let i = 0, s = 0, k = 0; i < n; i++, s = 0) {
for (let j = i; j < n; j++, k++) {
s += nums[j];
arr[k] = s;
}
}
arr = arr.sort((a, b) => a - b).slice(left - 1, right);
return arr.reduce((acc, cur) => (acc + cur) % mod, 0);
}func rangeSum(nums []int, n int, left int, right int) (ans int) {
var arr []int
for i := 0; i < n; i++ {
s := 0
for j := i; j < n; j++ {
s += nums[j]
arr = append(arr, s)
}
}
sort.Ints(arr)
const mod int = 1e9 + 7
for _, x := range arr[left-1 : right] {
ans = (ans + x) % mod
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Sorting | Time Complexity: O(n^2 log n) due to sorting. |
| Using Min-Heap for Efficient Range | Time Complexity: O(n^2 log right), as total subarray sums could be n^2 but managed within right for heap operations. |
| Simulation | – |
Complexity analysis
| 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 |
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.