Sum of Variable Length Subarrays

EASY

Description

You are given an integer array nums of size n. For each index i where 0 <= i < n, define a subarray nums[start ... i] where start = max(0, i - nums[i]).

Return the total sum of all elements from the subarray defined for each index in the array.

Example 1:

Input: nums = [2,3,1]

Output: 11

Explanation:

i	Subarray	Sum
0	`nums[0] = [2]`	2
1	`nums[0 ... 1] = [2, 3]`	5
2	`nums[1 ... 2] = [3, 1]`	4
Total Sum		11

The total sum is 11. Hence, 11 is the output.

Example 2:

Input: nums = [3,1,1,2]

Output: 13

Explanation:

i	Subarray	Sum
0	`nums[0] = [3]`	3
1	`nums[0 ... 1] = [3, 1]`	4
2	`nums[1 ... 2] = [1, 1]`	2
3	`nums[1 ... 3] = [1, 1, 2]`	4
Total Sum		13

The total sum is 13. Hence, 13 is the output.

Constraints:

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

Approaches

Checkout 2 different approaches to solve Sum of Variable Length Subarrays. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

This approach directly simulates the process described in the problem. We iterate through each index i of the array, determine the corresponding subarray by calculating its start and end points, and then iterate through this subarray to sum its elements. This sum is then added to a running total.

Algorithm

Initialize a variable totalSum to 0.
Loop through the input array nums with an outer loop from i = 0 to n-1.
Inside the outer loop, for each i, calculate the start index of the subarray: start = max(0, i - nums[i]).
Create an inner loop that iterates from j = start to i.
Inside the inner loop, add the value nums[j] to totalSum.
After both loops complete, totalSum will hold the final result.

The brute-force method is the most straightforward way to solve the problem. It follows the problem statement literally.

We initialize a variable, totalSum, to store the final answer.
We use a primary loop to iterate through each index i from 0 to n-1, where n is the length of the nums array. This loop corresponds to defining the subarray for each index.
For each i, we calculate the starting index start of the subarray as max(0, i - nums[i]).
We then use a nested loop to iterate from this start index up to i.
In this inner loop, we access each element nums[j] of the current subarray and add it to our totalSum.
After the outer loop finishes, totalSum contains the sum of all elements from all the defined subarrays.

class Solution {
    public int sumOfVariableLengthSubarrays(int[] nums) {
        int n = nums.length;
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            int start = Math.max(0, i - nums[i]);
            // Instead of a temporary sum, we can add directly to totalSum
            for (int j = start; j <= i; j++) {
                totalSum += nums[j];
            }
        }
        return totalSum;
    }
}

Complexity Analysis

Time Complexity: O(n^2). The outer loop runs `n` times. The inner loop's number of iterations depends on `nums[i]`, but in the worst-case scenario (e.g., if `nums[i]` is large for all `i`), it can run up to `n` times. This results in a nested loop structure leading to a quadratic time complexity.Space Complexity: O(1). We only use a few variables to store the loop indices and the running sum, requiring constant extra space regardless of the input size.

Pros and Cons

Pros:

Simple and easy to understand and implement.
Space-efficient as it uses constant extra space.
Sufficiently fast for the given constraints (n <= 100).

Cons:

Inefficient for larger input sizes as it repeatedly calculates sums over overlapping subarray portions.
The time complexity is quadratic, which might be too slow if the constraints were larger.

Code Solutions

Checking out 3 solutions in different languages for Sum of Variable Length Subarrays. Click on different languages to view the code.

class Solution {
public
  int subarraySum(int[] nums) {
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += s[i + 1] - s[Math.max(0, i - nums[i])];
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of Variable Length Subarrays

Patterns:

Prefix Sum

Data Structures:

Array