Range Sum Of Sorted Subarray Sums - Leetcode Solution

Problem Statement:

Given the array nums consisting of n positive integers, you need to compute the sum of all subarrays of nums sorted in non-decreasing order.

Example:

Input: nums = [1,2,3,4] Output: 20 Explanation: The sorted subarray sums are [1, 2, 3, 4, 3, 5, 6, 4, 7, 5, 9, 6, 10, 7, 11, 10, 15, 14, 20]. The sum of the subarrays is 20.

Solution:

To solve this problem, we will use the following approach:

1. We will create all the subarrays of the given array.

2. We will calculate the sum of all the subarrays.

3. We will store each sum in a separate array.

4. We will sort the sum array in non-decreasing order.

5. We will calculate the sum of the sorted sum array.

6. We will return the final sum as the output.

The time complexity of this approach is O(n^3logn).

Code:

class Solution {
public:
    int rangeSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums;
        
        for(int i=0 ; i<n ; i++){
            int sum = nums[i];
            sums.push_back(sum);
            for(int j=i+1 ; j<n ; j++){
                sum += nums[j];
                sums.push_back(sum);
            }
        }
        
        sort(sums.begin(), sums.end());
        
        long long ans = 0;
        long long mod = pow(10, 9) + 7;
        
        for(int i=0 ; i<sums.size() ; i++){
            ans = (ans + sums[i])%mod;
        }
        
        return ans;
    }
};

Optimized Solution:

To optimize the above solution, we can use the following approach:

1. We will create a prefix sum array for the given array.

2. We will create all the subarrays of the given array.

3. We will calculate the sum of all the subarrays.

4. We will store each sum in a separate array.

5. We will sort the sum array in non-decreasing order.

6. We will calculate the sum of the sorted sum array.

7. We will return the final sum as the output.

The time complexity of this approach is O(n^2logn).

Code:

class Solution {
public:
    int rangeSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix_sum(n+1, 0);
        
        for(int i=1 ; i<=n ; i++){
            prefix_sum[i] = prefix_sum[i-1] + nums[i-1];
        }
        
        vector<int> sums;
        
        for(int i=0 ; i<n ; i++){
            for(int j=i+1 ; j<=n ; j++){
                sums.push_back(prefix_sum[j] - prefix_sum[i]);
            }
        }
        
        sort(sums.begin(), sums.end());
        
        long long ans = 0;
        long long mod = pow(10, 9) + 7;
        
        for(int i=0 ; i<sums.size() ; i++){
            ans = (ans + sums[i])%mod;
        }
        
        return ans;
    }
};

1