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) / 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^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.length$
• $1 <= nums.length <= 1000$
• $1 <= nums[i] <= 100$
• $1 <= 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.

• Brute Force
• Min-Heap
• Fenwick Tree

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

JavaScript

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;
 }

TypeScript

Written by @manishh12

 function rangeSumOfSortedSubarraySums(nums: number[], n: number, left: number, right: number): number {
   const MOD = 1e9 + 7;
   const subarraySums: number[] = [];
   
   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;
 }

Python

Written by @manishh12

 from typing import List

 class Solution:
     def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
         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 = 0
         for i in range(left - 1, right):
             result = (result + subarray_sums[i]) % MOD
         
         return result

Java

Written by @manishh12

 import java.util.*;

 class Solution {
     public int rangeSum(int[] nums, int n, int left, int right) {
         final int MOD = 1000000007;
         List<Integer> subarraySums = new ArrayList<>();
         
         for (int i = 0; i < n; i++) {
             int sum = 0;
             for (int j = i; j < n; 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;
     }

 }

C++

Written by @manishh12

 #include <vector>
 #include <algorithm>

 using namespace std;

 class Solution {
 public:
     int rangeSum(vector<int>& nums, int n, int left, int right) {
         const int MOD = 1e9 + 7;
         vector<int> subarraySums;
         
         for (int i = 0; i < n; ++i) {
             int sum = 0;
             for (int j = i; j < n; ++j) {
                 sum += nums[j];
                 subarraySums.push_back(sum);
             }
         }
         
         sort(subarraySums.begin(), subarray

Sums.end());
         
         int result = 0;
         for (int 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

• LeetCode Problem: Range Sum of Sorted Subarray Sums
• Solution Link: Range Sum of Sorted Subarray Sums Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta