Range Sum of Sorted Subarray Sums - Practice Coding Problems

Range Sum of Sorted Subarray Sums - Problem

Array Two Pointers Binary Search Sorting Prefix Sum Medium

You are given an array nums consisting of n positive integers. You need to compute the sum of all non-empty continuous subarrays from the array and then sort 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4], left = 1, right = 5

› Output: 13

💡 Note: All subarray sums: [1]=1, [2]=2, [3]=3, [4]=4, [1,2]=3, [2,3]=5, [3,4]=7, [1,2,3]=6, [2,3,4]=9, [1,2,3,4]=10. Sorted: [1,2,3,3,4,5,6,7,9,10]. Sum from index 1 to 5: 1+2+3+3+4 = 13

Example 2 — Small Array

$ Input: nums = [1,2], left = 1, right = 3

› Output: 6

💡 Note: Subarray sums: [1]=1, [2]=2, [1,2]=3. Sorted: [1,2,3]. Sum from index 1 to 3: 1+2+3 = 6

Example 3 — Single Range

$ Input: nums = [1,2,3,4], left = 1, right = 10

› Output: 50

💡 Note: All 10 subarray sums: [1,2,3,3,4,5,6,7,9,10]. Sum of all elements: 1+2+3+3+4+5+6+7+9+10 = 50

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 100
1 ≤ left ≤ right ≤ n * (n + 1) / 2

Visualization

Tap to expand

Understanding the Visualization

Input

Original array [1,2,3,4] with range left=1, right=5

Generate & Sort

Create all subarray sums and sort them

Sum Range

Extract and sum elements from index 1 to 5

Key Takeaway

🎯 Key Insight: Generate all subarray sums, sort them, then extract the specified range sum

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to generate all possible subarray sums, sort them, then sum the specified range. The brute force approach generates all O(n²) subarray sums and sorts them in O(n² log n). The priority queue approach is more memory efficient for small ranges. Best approach depends on the size of the range vs array size. Time: O(n² log n), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Subarray Sums	O(n² log n)	O(n²)	Generate all possible subarray sums, sort them, then sum the range
Priority Queue Approach	O(right × log(right))	O(right)	Use min-heap to efficiently find the kth smallest subarray sums without storing all

Generate All Subarray Sums — Algorithm Steps

Generate all subarray sums using nested loops
Sort the sums array
Sum elements from left-1 to right-1 indices
Return result modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Sums

Create all subarray sums using nested loops

Sort

Sort all sums in ascending order

Sum Range

Sum elements from left to right indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    long long ia = *(const long long*)a;
    long long ib = *(const long long*)b;
    return (ia > ib) - (ia < ib);
}

int solution(int* nums, int numsSize, int left, int right) {
    const int MOD = 1000000007;
    int totalSums = numsSize * (numsSize + 1) / 2;
    long long* sums = (long long*)malloc(totalSums * sizeof(long long));
    int idx = 0;
    
    // Generate all subarray sums
    for (int i = 0; i < numsSize; i++) {
        long long currentSum = 0;
        for (int j = i; j < numsSize; j++) {
            currentSum += nums[j];
            sums[idx++] = currentSum;
        }
    }
    
    // Sort the sums
    qsort(sums, totalSums, sizeof(long long), compare);
    
    // Sum elements from left-1 to right-1 (convert to 0-indexed)
    long long result = 0;
    for (int i = left - 1; i < right; i++) {
        result = (result + sums[i]) % MOD;
    }
    
    free(sums);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int left, right;
    scanf("%d", &left);
    scanf("%d", &right);
    
    int result = solution(nums, numsSize, left, right);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

O(n²) to generate all subarray sums + O(n² log n) to sort them

⚠ Quadratic Growth

Space Complexity

O(n²)

Array to store all n*(n+1)/2 subarray sums

⚠ Quadratic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

742 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Subarray Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler