# Sum of Variable Length Subarrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-variable-length-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-variable-length-subarrays
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
The brute-force method is the most straightforward way to solve the problem. It follows the problem statement literally.

1.  We initialize a variable, `totalSum`, to store the final answer.
2.  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.
3.  For each `i`, we calculate the starting index `start` of the subarray as `max(0, i - nums[i])`.
4.  We then use a nested loop to iterate from this `start` index up to `i`.
5.  In this inner loop, we access each element `nums[j]` of the current subarray and add it to our `totalSum`.
6.  After the outer loop finishes, `totalSum` contains the sum of all elements from all the defined subarrays.

```java
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;
    }
}
```
### 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.

## Optimized Approach using Prefix Sums
This approach improves upon the brute-force method by avoiding redundant calculations. The main bottleneck in the previous approach was re-calculating the sum of subarrays in the inner loop. We can optimize this by pre-computing the prefix sums of the array. The sum of any subarray `nums[start...end]` can then be calculated in constant time.
**Time:** O(n). We have two separate loops, each running `n` times (or `n+1` times). The first loop computes the prefix sums, and the second loop calculates the total sum. Since the loops are not nested, the total time complexity is `O(n) + O(n) = O(n)`. · **Space:** O(n). We use an additional array of size `n+1` to store the prefix sums. The space required grows linearly with the size of the input array.
**Pros:** Highly time-efficient, with a linear time complexity.; Optimal solution in terms of time for any input size.
**Cons:** Requires extra space proportional to the input size to store the prefix sum array.
### Explanation
The core idea is that the sum of a subarray `nums[j...k]` can be found in `O(1)` time if we have pre-calculated the sum of all elements from the beginning of the array up to every index.

1.  First, we create a `prefixSum` array of size `n+1`. `prefixSum[i]` will store the sum of the first `i` elements of `nums` (i.e., `nums[0] + ... + nums[i-1]`).
2.  We initialize `prefixSum[0] = 0`. Then, we iterate from `i = 0` to `n-1` and calculate `prefixSum[i+1] = prefixSum[i] + nums[i]`. This populates the entire `prefixSum` array in `O(n)` time.
3.  With the `prefixSum` array, the sum of a subarray `nums[start...i]` is simply `prefixSum[i+1] - prefixSum[start]`.
4.  Now, we iterate through the `nums` array from `i = 0` to `n-1` as in the main problem.
5.  For each `i`, we calculate `start = max(0, i - nums[i])`.
6.  We find the subarray sum in `O(1)` time using our precomputed array: `subarraySum = prefixSum[i+1] - prefixSum[start]`.
7.  We add this `subarraySum` to the `totalSum`.
8.  This process avoids the nested loop, reducing the overall time complexity.

```java
class Solution {
    public int sumOfVariableLengthSubarrays(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            int start = Math.max(0, i - nums[i]);
            int subarraySum = prefixSum[i + 1] - prefixSum[start];
            totalSum += subarraySum;
        }
        return totalSum;
    }
}
```
### Algorithm
- Create a `prefixSum` array of size `n+1`, initialized to zeros.
- For `i` from `0` to `n-1`:
  - `prefixSum[i+1] = prefixSum[i] + nums[i]`.
- Initialize `totalSum = 0`.
- For `i` from `0` to `n-1`:
  - Calculate `start = max(0, i - nums[i])`.
  - Calculate `subarraySum = prefixSum[i+1] - prefixSum[start]`.
  - `totalSum += subarraySum`.
- Return `totalSum`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int subarraySum(vector<int> &nums) {
    int n = nums.size();
    vector<int> s(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[max(0, i - nums[i])];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def subarraySum(self, nums: List[int]) -> int: s = list(accumulate(nums, initial=0)) return sum(s[i + 1] - s[max(0, i - x)] for i, x in enumerate(nums))

```