Sum Subarrays Defined by Each Ending Value
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Given an integer array `nums` of length `n`, associate one subarray with every index `i`:
- Its right endpoint is `i`.
- Its left endpoint is `start = max(0, i - nums[i])`.
- Both endpoints are included.
Return the sum of the elements in all `n` associated subarrays. An element contributes again whenever it belongs to another associated subarray.
### C++ Interface
```cpp
class Solution {
public:
int subarraySum(vector<int>& nums) {
}
};
```
### Examples
**Example 1**
```text
Input: nums = [4,1,2,1]
Output: 19
```
| Index `i` | Associated subarray | Sum |
| --- | --- | --- |
| 0 | `[4]` | 4 |
| 1 | `[4,1]` | 5 |
| 2 | `[4,1,2]` | 7 |
| 3 | `[2,1]` | 3 |
The total is `4 + 5 + 7 + 3 = 19`.
**Example 2**
```text
Input: nums = [1,5]
Output: 7
```
At index `0`, the associated subarray is `[1]`. At index `1`, the computed left endpoint is clamped to `0`, giving `[1,5]`. Their sums are `1` and `6`, so the answer is `7`.
### Constraints
- `1 <= n == nums.length <= 100`.
- `1 <= nums[i] <= 1000`.
### Clarifying Questions
- Is `nums[i]` the subarray's length? No. It determines `i - nums[i]`; the right endpoint is also included.
- Can a left endpoint be negative? No. It is clamped to zero.
- Should an element shared by two associated subarrays be counted once? No. Each subarray contributes its entire sum independently.
### What a Strong Answer Covers
- The inclusive bounds and clamping rule for every index.
- Repeated contributions from overlapping associated subarrays.
- The one-element case and values of `nums[i]` larger than `i`.
- Correct total accumulation and resource bounds under the stated constraints.
### Follow-up Questions
- What would change in the definition if `nums[i]` specified a desired length rather than the distance back from `i`?
- If the same array were used for many batches of requested subarray bounds, what work could be shared between the batches?
```hint Reuse sums
A direct sum for each index fits these small constraints. To avoid adding the same earlier elements repeatedly, also consider cumulative sums ending just before each position.
```
Overview: Sum the inclusive subarray assigned to every index by its value, clamping each left boundary to zero. Count overlapping contributions independently and handle the original integer bounds.