Range Sum of Sorted Subarray Sums

Leetcode Problem:

• Range Sum of Sorted Subarray Sums

Summary

• Given an array of positive integers, compute the sum of all non-empty continuous subarrays, sort them, and return the sum of a specific range in the new array.

Approach

• The approach is to first compute the sum of all non-empty continuous subarrays, then sort them, and finally return the sum of the numbers in the specified range in the sorted array.

Complexity

• O(n^2 log n) due to sorting, where n is the number of elements in the input array.

Explain

• The solution code first initializes an empty array to store the subarray sums and a variable to store the sum of the current subarray
• It then iterates over the input array, adding each number to the current sum and pushing the sum to the array
• After each number is added, it also computes the sum of all possible subarrays starting from the current number and pushes these sums to the array
• Finally, it sorts the array and computes the sum of the numbers in the specified range.

Solution Code:

#define MOD 1000000007
class Solution {
public:
    int rangeSum(vector& nums, int n, int left, int right) {
        vector arr;
        long long sum = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            sum %= MOD;
            arr.push_back(sum);
            long long sum2 = 0;
            for(int j = i+1 ; j < nums.size(); j++){
                sum2 += nums[j];
                sum2 %= MOD;
                arr.push_back(sum2);
            }
        }
        sort(arr.begin(), arr.end());
        long long sum3 = 0;
        for(int i = left -1; i < right; i++){
            sum3 += arr[i];
            sum3 %= MOD;
        }
        return sum3;
    }
};