Range Sum of Sorted Subarray Sums

medium sorting prefix sum subarray

Problem

Given an array nums of n positive integers, compute the sum of every non-empty continuous subarray and sort all n·(n+1)/2 of those sums in non-decreasing order. Return the sum of the values from index left to index right (1-indexed), inclusive, in that sorted array, modulo 10⁹ + 7.

Inputnums = [1,2,3,4], left = 1, right = 5

Output13

Subarray sums sorted: [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. Indices 1..5 are 1 + 2 + 3 + 3 + 4 = 13.

Inputnums = [1,2,3,4], left = 3, right = 4

Output6

Same sorted array; indices 3..4 are 3 + 3 = 6.

nums (comma-separated)

left (1-indexed)

right (1-indexed)

def range_sum(nums, n, left, right):
    MOD = 10**9 + 7
    sums = []
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            sums.append(s)
    sums.sort()
    total = 0
    for k in range(left - 1, right):
        total += sums[k]
    return total % MOD

function rangeSum(nums, n, left, right) {
  const MOD = 1000000007n;
  const sums = [];
  for (let i = 0; i < n; i++) {
    let s = 0;
    for (let j = i; j < n; j++) {
      s += nums[j];
      sums.push(s);
    }
  }
  sums.sort((a, b) => a - b);
  let total = 0n;
  for (let k = left - 1; k < right; k++) {
    total += BigInt(sums[k]);
  }
  return Number(total % MOD);
}

int rangeSum(int[] nums, int n, int left, int right) {
    final int MOD = 1_000_000_007;
    int[] sums = new int[n * (n + 1) / 2];
    int idx = 0;
    for (int i = 0; i < n; i++) {
        int s = 0;
        for (int j = i; j < n; j++) {
            s += nums[j];
            sums[idx++] = s;
        }
    }
    Arrays.sort(sums);
    long total = 0;
    for (int k = left - 1; k < right; k++) {
        total += sums[k];
    }
    return (int) (total % MOD);
}

int rangeSum(vector<int>& nums, int n, int left, int right) {
    const int MOD = 1e9 + 7;
    vector<int> sums;
    for (int i = 0; i < n; i++) {
        int s = 0;
        for (int j = i; j < n; j++) {
            s += nums[j];
            sums.push_back(s);
        }
    }
    sort(sums.begin(), sums.end());
    long long total = 0;
    for (int k = left - 1; k < right; k++) {
        total += sums[k];
    }
    return (int) (total % MOD);
}

Explanation

The constraints are small (n ≤ 1000), so the most direct correct approach is to materialize every subarray sum, sort the whole list, and read off the requested range.

To enumerate sums efficiently we fix a start index i and extend the end index j from i to n − 1, keeping a running sum s. Each time we extend, s is the sum of the subarray nums[i..j], so we record it. This produces all n·(n+1)/2 sums in O(n²) time without recomputing anything.

Next we sort the collected sums in non-decreasing order. Sorting is what makes the index range meaningful — the same multiset of sums becomes a fixed ordered sequence.

Because left and right are 1-indexed, we add up sums[left − 1 .. right − 1]. A running accumulator handles this in one pass; conceptually it is a prefix-sum range query over the sorted array.

Finally we return the total modulo 10⁹ + 7, since the answer can be large. Overall cost is dominated by the sort: O(n² log n) time and O(n²) space for the list of sums.

Time: O(n² log n) Space: O(n²)