Solution: Range Sum of Sorted Subarray Sums

Statement

You are given an integer array nums containing $n$ positive integers along with left and right. Calculate the sum of its elements for every non-empty continuous subarray of nums. Collect these sums into a new array and sort it in nondecreasing order. This will result in a new array of size $n \times (n + 1) /2$.

Your task is to return the sum of the elements in this sorted array from the index left to right (inclusive with 1-based indexing).

Note: As the result can be large, return the sum modulo $10^9 + 7$.

Constraints:

• $n =$ nums.length

• $1 \leq$ nums.length $\leq 1000$

• $1 \leq$ nums[i] $\leq 100$

• $1 \leq$ left $\leq$ right $\leq n \times (n + 1) / 2$

Solution

In a brute-force approach, you would generate all possible subarrays, calculate their sums, and sort these sums to find the range sum between the indexes left and right. However, this method is inefficient as the number of subarrays grows quadratically with the size of the array.

Instead, we optimize the process using binary search to directly find the range sum without calculating or sorting all the subarray sums. We start by identifying a feasible range for possible subarray sums, which lies between the smallest element in the array, min(nums), and the total sum of the array, sum(nums). This range is necessary as it includes every possible subarray sum, ensuring no valid sums are overlooked and serving as the foundation for the binary search.

For each threshold, we calculate the count of subarrays with sums below the threshold and their cumulative sum using a sliding window technique. Why do we apply binary search? The goal is to find a threshold value $T$ such that there are exactly $k$ subarrays with sums less than or equal to $T$. The binary search narrows this threshold by checking for each mid value (potential sum threshold) if it satisfies the condition of having at least $k$ subarrays below it. By adjusting the search range based on the count, we pinpoint the boundaries of the desired range of subarray sums.

Once we calculate the total sum of subarrays up to index right and the total sum of subarrays up to index left - 1, we subtract these two sums to get the sum of the subarrays in the range [left, right].

Following are the implementation steps of the algorithm—categorized into three main sections:

1. Finding the threshold for k smallest subarray sums:

   1. We start by determining the cutoff value that separates the smallest $k$ subarray sums from the rest. We do this by defining the minimum possible sum, minSum, as the smallest element in the array and the maximum sum, maxSum, as the total sum of all elements in the array.

   2. Next, we perform a binary search:

      1. We compute the midpoint of the current range by: $\text{mid} = \text{TLeft} + (\text{TRight} - \text{TLeft}) // 2$

      2. Next, we use the countAndSum function to find:

         1. The number of subarray sums, count, that is less than or equal to this midpoint.

         2. The cumulative sum, totalSum, of these subarrays.

      3. We then adjust the search range based on the count of subarray sums:

         1. If there are at least $k$ valid subarrays, we reduce the upper bound, TRight, to focus on smaller sums by assigning mid - 1 to TRight.

         2. Otherwise, increase the lower bound, TLeft, to consider larger sums by assigning mid + 1 to TLeft.

         3. This process continues until the range converges, pinpointing the boundaries of the desired range.

   3. After the binary search converges, use the countAndSum function again to refine the sum of exactly the first subarray sums.

2. Count and sum subarray sums using the sliding window:

   1. To avoid generating all subarray sums explicitly, we use a sliding window approach:

      1. We maintain a running sum, currentSum, and the cumulative contribution of subarray sums, windowSum, for the current window.

      2. For every new element, nums[j], in the array:

         1. Add it to the running sum and update the window sum using: $\text{windowSum} += \text{nums}[j] * (j - i + 1)$.

         2. If the running sum exceeds the given threshold, i,e., if currentSum > target, we shrink the window from the left by subtracting currentSum from windowSum until it is valid again.

            1. Remove nums[i] from currentSum and increment i.

      3. Then, we incrementally add the sums of all valid subarrays ending at the current element to the total.

   2. Next, we return count and totalSum for the given target. This method ensures that we calculate subarray sums dynamically without needing explicit storage.

3. Computing the result for the desired range:

   1. To get the final sum of subarray sums between indexes left and right:

      1. We call sumOfFirstK(nums, n, right) to compute the sum of subarrays up to the right.

      2. And sumOfFirstK(nums, n, left - 1) to compute the cumulative sum up to left - 1.

      3. Then, we subtract these two results to get the sum of all subarray sums within the desired range.

   2. Finally, we return the result modulo to handle potential overflow.

Let’s look at the following illustration to get a better understanding of the solution: