Problem of The Day: Range Sum of Sorted Subarray Sums

Problem Statement

Intuition

To find the sum of a specific range of subarray sums, we can first generate all possible subarray sums, sort them, and then sum the desired range.

Approach

1. Generate Subarray Sums: Iterate through the array and calculate the sum of all subarrays.
2. Sort the Sums: Sort the list of subarray sums to make it easy to access the required range.
3. Sum the Desired Range: Sum the elements from the left index to the right index in the sorted list of subarray sums.

Complexity

• Time Complexity:
  • Generating all subarray sums takes (O(n^2)) time since there are (\frac{n(n+1)}{2}) subarrays.
  • Sorting the subarray sums takes (O(n^2 \log n)).
  • Summing a range of the sorted array is (O(right - left + 1)), which is (O(n^2)) in the worst case.
  • Overall time complexity: (O(n^2 \log n)).
• Space Complexity:
  • Storing all subarray sums requires (O(n^2)) space.
  • Overall space complexity: (O(n^2)).

Code

from typing import List

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        sub_arr = []
        MOD = 10**9 + 7
        for i in range(n):
            curr_sum = 0
            for j in range(i, n):
                curr_sum += nums[j]
                sub_arr.append(curr_sum)

        sub_arr_sorted = sorted(sub_arr)
        return sum(sub_arr_sorted[left-1:right]) % MOD

Editorial

Approach 2: Priority Queue

class Solution:
    import heapq

    def rangeSum(self, nums, n, left, right):
        pq = []
        for i in range(n):
            heapq.heappush(pq, (nums[i], i))

        ans = 0
        mod = 1e9 + 7
        for i in range(1, right + 1):
            p = heapq.heappop(pq)
            # If the current index is greater than or equal to left, add the
            # value to the answer.
            if i >= left:
                ans = (ans + p[0]) % mod
            # If index is less than the last index, increment it and add its
            # value to the first pair value.
            if p[1] < n - 1:
                p = (p[0] + nums[p[1] + 1], p[1] + 1)
                heapq.heappush(pq, p)
        return int(ans)

• time: O(n^2 * logn)
• space: O(n)

Approach 3: Binary Search and Sliding Window

class Solution:
    def rangeSum(self, nums, n, left, right):
        mod = 10**9 + 7

        def count_and_sum(nums, n, target):
            count = 0
            current_sum = 0
            total_sum = 0
            window_sum = 0
            i = 0
            for j in range(n):
                current_sum += nums[j]
                window_sum += nums[j] * (j - i + 1)
                while current_sum > target:
                    window_sum -= current_sum
                    current_sum -= nums[i]
                    i += 1
                count += j - i + 1
                total_sum += window_sum
            return count, total_sum

        def sum_of_first_k(nums, n, k):
            min_sum = min(nums)
            max_sum = sum(nums)
            left = min_sum
            right = max_sum

            while left <= right:
                mid = left + (right - left) // 2
                if count_and_sum(nums, n, mid)[0] >= k:
                    right = mid - 1
                else:
                    left = mid + 1
            count, total_sum = count_and_sum(nums, n, left)
            # There can be more subarrays with the same sum of left.
            return total_sum - left * (count - k)

        result = (
            sum_of_first_k(nums, n, right) - sum_of_first_k(nums, n, left - 1)
        ) % mod
        # Ensure non-negative result
        return (result + mod) % mod

• time: O(n log sum) where n is the the size and sum is the total sum of the sums array
• space: O(1)