Range Sum of Sorted Subarray Sums in C++

Explore More Solutions

Problem Description

Welcome to the world of subarrays, where every slice of your array is a potential goldmine of sums! The problem at hand is like trying to find the best deals in a supermarket, but instead of groceries, we’re hunting for subarray sums. The task is to calculate the sum of all subarray sums that fall within a specified range.

Imagine you’re at a buffet, and you can only eat the dishes that fall within a certain calorie range. You want to know how many calories you can consume without going overboard. Similarly, in this problem, we want to find the sum of all subarray sums that lie between two given indices, left and right.

So, if you’ve ever tried to count how many cookies you can eat without feeling guilty, you’ll understand the essence of this problem!

Code Solution


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

    auto subarraysAndSumNoGreaterThan = [&](int m) -> pair {
      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};
    };

    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);
      return total - l * (count - k);
    };

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

Approach Explanation

The code employs a clever approach using a sliding window technique combined with binary search. It calculates the number of subarrays whose sums are less than or equal to a given value m. By adjusting the window size dynamically, it efficiently counts and sums the subarrays. The main function then uses this helper function to find the total sum of subarrays that fall within the specified range.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(1)

Real-World Example

Think of this problem like planning a road trip where you want to calculate the total distance you can travel without exceeding a certain mileage limit. Each subarray represents a segment of your journey, and you want to know how far you can go without hitting that dreaded "low fuel" warning. The solution helps you sum up all those segments that keep you within your mileage budget!