We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Range Sum of Sorted Subarray Sums

Number: 1615

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Amazon

Problem Description

Given an array nums of n positive integers, consider all non-empty continuous subarrays and their sums. After computing these sums, they are sorted in non-decreasing order to form a new array of length n * (n + 1) / 2. The task is to return the sum of the numbers in the sorted array from index left to index right (1-indexed) modulo 10^9 + 7.

Key Insights

  • The total number of subarray sums is O(n^2), which for n up to 1000 results in at most ~500,500 numbers.
  • A straightforward brute-force approach can use prefix sums to compute continuous subarray sums in O(n^2) time.
  • Sorting all subarray sums has a complexity of O(n^2 log(n^2)) which is acceptable given the input constraints.
  • Take care of the 1-indexed positions when extracting the required sum.
  • The modulo operation is used at the end to handle very large values.

Space and Time Complexity

Time Complexity: O(n^2 log(n^2)) – O(n^2) for generating subarray sums and O(n^2 log(n^2)) for sorting
Space Complexity: O(n^2) – space is needed to store all subarray sums

Solution

We compute all possible subarray sums using a nested loop; using prefix sums can optimize the inner summation. Once we have accumulated the subarray sums into an array, we sort them. The next step is to extract the portion from index left-1 to right-1 (since the problem is 1-indexed) and compute their sum modulo 10^9 + 7.

Data structures used:

  • Array: to store all subarray sums
  • Variables for prefix sum accumulation
    Algorithmic approaches:
  • Use nested loops with a running sum to compute subarray sums.
  • Sort the resultant array of sums.
  • Sum the required slice and apply the modulo operation.

Tricks/Gotchas:

  • Watch for off-by-one errors due to the 1-indexed requirement.
  • Ensure modulo is applied to avoid integer overflow.

Code Solutions

# Function to compute the range sum of sorted subarray sums
def rangeSum(nums, n, left, right):
    MOD = 10**9 + 7
    subarray_sums = []
    
    # Compute all possible subarray sums
    for i in range(n):
        curr_sum = 0
        # Generate sums for subarrays starting at index i
        for j in range(i, n):
            curr_sum += nums[j]
            subarray_sums.append(curr_sum)
    
    # Sort the subarray sums
    subarray_sums.sort()
    
    # Calculate the sum for the subarray from left-1 to right-1 (1-indexed to 0-indexed)
    total = sum(subarray_sums[left-1:right]) % MOD
    return total

# Example usage:
nums = [1,2,3,4]
n = 4
left = 1
right = 5
print(rangeSum(nums, n, left, right))  # Expected output: 13
← Back to All Questions