Skip to main content

Range Sum of Sorted Subarray Sums

In this page, we will solve the Range Sum of Sorted Subarray Sums problem using different approaches: calculating all subarray sums and sorting them, and using a min-heap for efficiency. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description​

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)/2n * (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)(10^9 + 7).

Examples​

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 left = 1 to right = 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 left = 3 to right = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Constraints​

  • n==nums.lengthn == nums.length
  • 1<=nums.length<=10001 <= nums.length <= 1000
  • 1<=nums[i]<=1001 <= nums[i] <= 100
  • 1<=left<=right<=n∗(n+1)/21 <= left <= right <= n * (n + 1) / 2

Explanation​

There are three main approaches discussed:

  1. Naive Approach:

    • Calculate all possible subarray sums and store them in a list.
    • Sort the list of subarray sums.
    • Calculate the sum of the range of sorted subarray sums from left to right.
  2. Min-Heap Approach:

    • Use a min-heap to store the subarray sums dynamically.
    • Extract the minimum elements from the heap for the required range and sum them up.
  3. Fenwick Tree Approach:

    • Use a Fenwick Tree to manage prefix sums.
    • Calculate subarray sums based on prefix sums.
    • Sort the subarray sums and sum the elements in the required range.

Solution for Range Sum of Sorted Subarray Sums​

Intuition and Approach​

To solve the problem, we can use two approaches:

  1. Brute Force Approach: Calculate all subarray sums, sort them, and then find the sum of the specified range.
  2. Optimized Approach Using Min-Heap: Use a min-heap to keep track of the smallest sums and avoid sorting the entire list of subarray sums.

Approach 1: Brute Force​

Implementation​

Live Editor
function rangeSumNaive() {
  function rangeSum(nums, n, left, right) {
    const MOD = 1e9 + 7;
    const allSums = [];
    
    for (let i = 0; i < n; i++) {
      let sum = 0;
      for (let j = i; j < n; j++) {
        sum += nums[j];
        allSums.push(sum);
      }
    }
    
    allSums.sort((a, b) => a - b);
    
    let result = 0;
    for (let i = left - 1; i < right; i++) {
      result = (result + allSums[i]) % MOD;
    }
    
    return result;
  }

  const nums = [1, 2, 3, 4];
  const n = 4, left = 1, right = 5;
  const result = rangeSum(nums, n, left, right);

  return (
    <div>
      <p>
        <b>Input:</b> {JSON.stringify(nums)}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}

Result
Loading...

Code in Different Languages​

Written by @manishh12
 function rangeSumOfSortedSubarraySums(nums, n, left, right) {
const MOD = 1e9 + 7;
const 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;
}
tip

Each approach has its own time and space complexity considerations. The naive approach is simple but may be inefficient for large inputs. The min-heap approach optimizes the process of finding the smallest subarray sums. The Fenwick Tree approach efficiently manages prefix sums but requires understanding of Fenwick Tree operations.

References​