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

Sum of Variable Length Subarrays

Number: 3731

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers nums, for each index i (0 <= i < n), define a subarray as nums[start ... i] where start = max(0, i - nums[i]). The task is to calculate the total sum of all elements in these subarrays.

Key Insights

  • For each index i, the start of the subarray is determined by max(0, i - nums[i]).
  • Instead of summing every subarray using a nested loop, a prefix sum array can be used to efficiently compute the sum in O(1) time per query.
  • Boundary handling is needed for the case when the subarray begins at index 0.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array (prefix sum computation and one pass over the array)
Space Complexity: O(n), for storing the prefix sum array

Solution

We compute a prefix sum array such that prefix[i] represents the sum of the first i+1 elements of nums. For each index i, the desired subarray is from start = max(0, i - nums[i]) to i. The sum for that subarray is calculated as prefix[i] minus prefix[start-1] (if start > 0, otherwise just prefix[i]). Summing these results for each index gives the final answer. This method leverages the prefix sum to avoid recomputation and achieve optimal performance.

Code Solutions

def sum_variable_length_subarrays(nums):
    # Calculate prefix sum array where prefix[i] is sum of nums[0 ... i]
    n = len(nums)
    prefix = [0] * n
    prefix[0] = nums[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + nums[i]
    
    total_sum = 0
    # Compute the total sum using the prefix sum array
    for i in range(n):
        start = max(0, i - nums[i])
        # If start is 0, no need to subtract; otherwise subtract prefix[start-1]
        subarray_sum = prefix[i] - (prefix[start - 1] if start > 0 else 0)
        total_sum += subarray_sum
    
    return total_sum

# Example usage:
print(sum_variable_length_subarrays([2, 3, 1]))  # Expected output: 11
← Back to All Questions