1508. Range Sum of Sorted Subarray Sums LeetCode Solution

In this guide, you will get 1508. Range Sum of Sorted Subarray Sums LeetCode Solution with the best time and space complexity. The solution to Range Sum of Sorted Subarray Sums problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Range Sum of Sorted Subarray Sums solution in C++
Range Sum of Sorted Subarray Sums solution in Java
Range Sum of Sorted Subarray Sums solution in Python
Additional Resources

1508. Range Sum of Sorted Subarray Sums LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(1)

1508. Range Sum of Sorted Subarray Sums LeetCode Solution in C++

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

    auto subarraysAndSumNoGreaterThan = [&](int m) -> pair<int, long> {
      int count = 0;   // the number of subarrays <= m
      long total = 0;  // sum(subarrays)
      int sum = 0;     // the current sum
      int window = 0;  // the window sum

      for (int i = 0, j = 0; j < n; ++j) {
        sum += nums[j] * (j - i + 1);
        window += nums[j];  // Extend each subarray that ends in j.
        while (window > m) {
          sum -= window;
          window -= nums[i++];  // Shrink the window.
        }
        count += j - i + 1;
        total += sum;
      }

      return {count, total};
    };

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

    auto firstKSubarraysSum = [&](int k) -> long {
      int l = L;
      int r = R;

      while (l < r) {
        const int m = l + (r - l) / 2;
        if (subarraysAndSumNoGreaterThan(m).first < k)
          l = m + 1;
        else
          r = m;
      }

      const auto& [count, total] = subarraysAndSumNoGreaterThan(l);
      // If count != k, there're subarray(s) have the same sum as l.
      return total - l * (count - k);
    };

    return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1)) % kMod;
  }
};
/* code provided by PROGIEZ */