Scale Engineer

Range Sum of Sorted Subarray Sums

Med
#1391Time: O(n^2 log n) - Generating all subarray sums takes O(n^2). The number of sums is `N = n * (n + 1) / 2`, which is O(n^2). Sorting these `N` sums takes O(N log N) = O(n^2 log(n^2)) = O(n^2 log n). Summing the required range takes O(right - left), which is at most O(n^2). The sorting step dominates the complexity.Space: O(n^2) - We need to store all `n * (n + 1) / 2` subarray sums in a list.
Patterns
Two PointersPrefix Sum
Algorithms
Binary SearchSorting
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. First, we generate all possible non-empty continuous subarray sums. Then, we sort these sums in non-decreasing order. Finally, we iterate through the sorted list from the left-th to the right-th element (1-indexed) and accumulate their sum.

Algorithm

  • Create an empty list, say sums, to store all subarray sums.
  • Iterate through the input array nums with a starting index i from 0 to n-1.
  • For each i, start a nested loop with an ending index j from i to n-1.
  • Maintain a currentSum for the subarray starting at i. In the inner loop, add nums[j] to currentSum and add this currentSum to the sums list.
  • After generating all n * (n + 1) / 2 sums, sort the sums list in non-decreasing order.
  • Initialize a variable result to 0.
  • Iterate from k = left - 1 to right - 1 (using 0-based indexing for the list).
  • Add sums.get(k) to result, taking the modulo 10^9 + 7 at each step to prevent overflow.
  • Return result.

Walkthrough

The simplest way to solve this problem is to follow the instructions literally. We can use two nested loops to generate every possible continuous subarray. The outer loop picks the starting element, and the inner loop expands the subarray to the right. For each subarray, we calculate its sum and store it in a list. After generating all n * (n + 1) / 2 sums, we sort this list. Finally, we sum up the elements from index left - 1 to right - 1 in the sorted list, applying the modulo operation at each addition to handle potentially large sums.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int rangeSum(int[] nums, int n, int left, int right) {        int MOD = 1_000_000_007;        List<Integer> sums = new ArrayList<>();                for (int i = 0; i < n; i++) {            int currentSum = 0;            for (int j = i; j < n; j++) {                currentSum += nums[j];                sums.add(currentSum);            }        }                Collections.sort(sums);                long result = 0;        for (int i = left - 1; i < right; i++) {            result = (result + sums.get(i)) % MOD;        }                return (int) result;    }}

Complexity

Time

O(n^2 log n) - Generating all subarray sums takes O(n^2). The number of sums is `N = n * (n + 1) / 2`, which is O(n^2). Sorting these `N` sums takes O(N log N) = O(n^2 log(n^2)) = O(n^2 log n). Summing the required range takes O(right - left), which is at most O(n^2). The sorting step dominates the complexity.

Space

O(n^2) - We need to store all `n * (n + 1) / 2` subarray sums in a list.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem statement.

Cons

  • Inefficient in both time and space, especially for large n.

  • May result in Time Limit Exceeded or Memory Limit Exceeded for larger constraints.

Solutions

class Solution {public  int rangeSum(int[] nums, int n, int left, int right) {    int[] arr = new int[n * (n + 1) / 2];    for (int i = 0, k = 0; i < n; ++i) {      int s = 0;      for (int j = i; j < n; ++j) {        s += nums[j];        arr[k++] = s;      }    }    Arrays.sort(arr);    int ans = 0;    final int mod = (int)1 e9 + 7;    for (int i = left - 1; i < right; ++i) {      ans = (ans + arr[i]) % mod;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem