Sum of Variable Length Subarrays

Difficulty: Easy | Acceptance: 85.60% | Paid: No Topics: Array, Prefix Sum

You are given a 0-indexed integer array nums and an array lengths of the same length.

For each index i, you need to consider the subarray of nums starting at index i with length lengths[i]. If the length lengths[i] causes the subarray to go beyond the bounds of nums, consider only the elements up to the last index of nums.

Return the sum of all elements in all these subarrays.

• Examples
• Constraints
• Brute Force Simulation
• Prefix Sum Optimization
• Difference Array (Contribution Counting)

Examples

Example 1:

Input: nums = [1,2,3,4], lengths = [1,3,1,2]
Output: 17
Explanation:
- Subarray at index 0 with length 1: [1]. Sum = 1.
- Subarray at index 1 with length 3: [2, 3, 4]. Sum = 9.
- Subarray at index 2 with length 1: [3]. Sum = 3.
- Subarray at index 3 with length 2: [4]. (Only 1 element remains). Sum = 4.
Total sum = 1 + 9 + 3 + 4 = 17.

Example 2:

Input: nums = [1,2,3], lengths = [3,3,3]
Output: 14
Explanation:
- Subarray at index 0 with length 3: [1, 2, 3]. Sum = 6.
- Subarray at index 1 with length 3: [2, 3]. Sum = 5.
- Subarray at index 2 with length 3: [3]. Sum = 3.
Total sum = 6 + 5 + 3 = 14.

Constraints

- 1 <= n == nums.length <= 100
- 1 <= nums[i] <= 1000

Brute Force Simulation

Intuition Iterate through each starting index i, determine the end of the subarray based on lengths[i], and sum the elements directly by iterating through the subarray.

Steps

• Initialize total to 0.
• Iterate through each index i from 0 to n-1.
• Calculate the end index j as min(n-1, i + lengths[i] - 1).
• Iterate from i to j and add nums[k] to total.
• Return total.

class Solution:
    def sumOfSubarrays(self, nums: list[int], lengths: list[int]) -> int:
        n = len(nums)
        total = 0
        for i in range(n):
            end = min(n - 1, i + lengths[i] - 1)
            for j in range(i, end + 1):
                total += nums[j]
        return total

Complexity

• Time: O(n * L) where L is the average length. In the worst case, this is O(n²).
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays or large lengths.

Prefix Sum Optimization

Intuition Precompute the prefix sums of the array to allow calculating the sum of any subarray in constant time. This avoids the inner loop of the brute force approach.

Steps

• Create a prefix array where prefix[i] is the sum of elements from nums[0] to nums[i-1].
• Iterate through each index i.
• Calculate the end index j as min(n-1, i + lengths[i] - 1).
• Add prefix[j+1] - prefix[i] to total.
• Return total.

class Solution:
    def sumOfSubarrays(self, nums: list[int], lengths: list[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        total = 0
        for i in range(n):
            end = min(n - 1, i + lengths[i] - 1)
            total += prefix[end + 1] - prefix[i]
        return total

Complexity

• Time: O(n) for building prefix sum and O(n) for calculating total, resulting in O(n).
• Space: O(n) for the prefix array.
• Notes: Efficient time complexity, optimal for this problem type.

Difference Array (Contribution Counting)

Intuition Instead of summing subarrays, determine how many times each element nums[i] contributes to the final total. An element nums[i] is included in the subarray starting at j if j <= i and j + lengths[j] > i. We can use a difference array to mark the ranges covered by each subarray.

Steps

• Initialize a difference array diff of size n+1 with zeros.
• Iterate through each index i (start of subarray).
• Calculate the end index j as min(n-1, i + lengths[i] - 1).
• Increment diff[i] by 1 and decrement diff[j+1] by 1.
• Compute the prefix sum of the diff array to get the count of how many subarrays cover each index i.
• Multiply the count at index i by nums[i] and add to total.

class Solution:
    def sumOfSubarrays(self, nums: list[int], lengths: list[int]) -> int:
        n = len(nums)
        diff = [0] * (n + 1)
        
        for i in range(n):
            end = min(n - 1, i + lengths[i] - 1)
            diff[i] += 1
            diff[end + 1] -= 1
        
        total = 0
        count = 0
        for i in range(n):
            count += diff[i]
            total += count * nums[i]
        return total

Complexity

• Time: O(n) to process ranges and O(n) to calculate the total, resulting in O(n).
• Space: O(n) for the difference array.
• Notes: A clever approach that transforms the problem into a range update query.