1508. Range Sum of Sorted Subarray Sums

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 109 + 7.

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 le = 1 to ri = 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 le = 3 to ri = 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

Approach 01:

#include <vector>
#include <numeric>
#include <algorithm>
#include <ranges>

using namespace std;

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        constexpr int kMod = 1'000'000'007;

        // Helper function to count subarrays with sums no greater than `threshold`
        // and to calculate the sum of these subarrays
        auto subarraysAndSumNoGreaterThan = [&](int threshold) -> pair<int, long> {
            int subarrayCount = 0;  // Number of subarrays with sums <= threshold
            long totalSum = 0;      // Sum of these subarrays
            int currentSum = 0;     // Current sum of the subarray
            int windowSum = 0;      // Window sum

            for (int start = 0, end = 0; end < n; ++end) {
                currentSum += nums[end] * (end - start + 1);
                windowSum += nums[end];  // Extend each subarray that ends at `end`
                while (windowSum > threshold) {
                    currentSum -= windowSum;
                    windowSum -= nums[start++];  // Shrink the window
                }
                subarrayCount += end - start + 1;
                totalSum += currentSum;
            }

            return {subarrayCount, totalSum};
        };

        // [minSum, maxSum] is the possible range of the sum of any subarray
        const int minSum = ranges::min(nums);
        const int maxSum = accumulate(nums.begin(), nums.end(), 0);

        // Helper function to find the sum of the first `k` subarrays with the smallest sums
        auto firstKSubarraysSum = [&](int k) -> long {
            int low = minSum;
            int high = maxSum;

            while (low < high) {
                const int mid = low + (high - low) / 2;
                if (subarraysAndSumNoGreaterThan(mid).first < k)
                    low = mid + 1;
                else
                    high = mid;
            }

            const auto& [count, total] = subarraysAndSumNoGreaterThan(low);
            // If `count` != `k`, there are subarrays with the same sum as `low`
            return total - low * (count - k);
        };

        return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1)) % kMod;
    }
};

from typing import List, Tuple

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        kMod = 1_000_000_007

        # Helper function to count subarrays with sums no greater than `threshold`
        # and to calculate the sum of these subarrays
        def subarraysAndSumNoGreaterThan(threshold: int) -> Tuple[int, int]:
            subarrayCount = 0  # Number of subarrays with sums <= threshold
            totalSum = 0  # Sum of these subarrays
            currentSum = 0  # Current sum of the subarray
            windowSum = 0  # Window sum

            start = 0
            for end in range(n):
                currentSum += nums[end] * (end - start + 1)
                windowSum += nums[end]  # Extend each subarray that ends at `end`
                while windowSum > threshold:
                    currentSum -= windowSum
                    windowSum -= nums[start]  # Shrink the window
                    start += 1
                subarrayCount += end - start + 1
                totalSum += currentSum

            return subarrayCount, totalSum

        # [minSum, maxSum] is the possible range of the sum of any subarray
        minSum = min(nums)
        maxSum = sum(nums)

        # Helper function to find the sum of the first `k` subarrays with the smallest sums
        def firstKSubarraysSum(k: int) -> int:
            low = minSum
            high = maxSum

            while low < high:
                mid = low + (high - low) // 2
                if subarraysAndSumNoGreaterThan(mid)[0] < k:
                    low = mid + 1
                else:
                    high = mid

            count, total = subarraysAndSumNoGreaterThan(low)
            # If `count` != `k`, there are subarrays with the same sum as `low`
            return total - low * (count - k)

        return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1)) % kMod

Time Complexity

• Subarray Sum Calculation:

  The helper function subarraysAndSumNoGreaterThan runs in \( O(n) \) time for each invocation, where \( n \) is the length of the array. This is because it iterates through the array and maintains a sliding window to calculate subarray sums.

• Binary Search:

  The firstKSubarraysSum function uses a binary search to find the k-th smallest subarray sum. The binary search runs in \( O(\log(\text{maxSum} – \text{minSum})) \) iterations. For each iteration, it invokes subarraysAndSumNoGreaterThan, which takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(n \log(\text{maxSum} – \text{minSum})) \). Since firstKSubarraysSum is called twice (for right and left-1), the constant factor is 2, but the complexity remains \( O(n \log(\text{maxSum} – \text{minSum})) \).

Space Complexity

• Auxiliary Space:

  The space complexity is \( O(1) \) since we only use a few additional variables to maintain the current sum, window sum, subarray count, and total sum.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \) as we do not use any extra space proportional to the input size.