# LeetCode 325: Maximum Size Subarray Sum Equals k

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

Return the maximum length of a contiguous subarray whose sum equals `k`.

If no such subarray exists, return `0`.

A subarray must be contiguous. The official examples include `nums = [1, -1, 5, -2, 3]`, `k = 3`, whose answer is `4`, because `[1, -1, 5, -2]` sums to `3` and is the longest. The problem also notes that the total sum of the array fits in a 32-bit signed integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `k` |
| Output | Maximum length of a subarray whose sum is `k` |
| If none exists | Return `0` |
| Subarray rule | Elements must be contiguous |
| Values | Can include positive, negative, and zero |

Function shape:

```python
def maxSubArrayLen(nums: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, -1, 5, -2, 3]
k = 3
```

The subarray:

```python
[1, -1, 5, -2]
```

has sum:

```python
1 + (-1) + 5 + (-2) = 3
```

Its length is `4`.

Output:

```python
4
```

Example 2:

```python
nums = [-2, -1, 2, 1]
k = 1
```

The subarray:

```python
[-1, 2]
```

has sum:

```python
-1 + 2 = 1
```

Its length is `2`.

Output:

```python
2
```

Example 3:

```python
nums = [1, 2, 3]
k = 7
```

No subarray sums to `7`.

Output:

```python
0
```

## First Thought: Check Every Subarray

A direct solution checks every possible subarray.

For each start index, keep extending the end index and update the running sum.

```python
answer = 0

for left in range(len(nums)):
    total = 0

    for right in range(left, len(nums)):
        total += nums[right]

        if total == k:
            answer = max(answer, right - left + 1)
```

This works.

But it costs `O(n^2)` time.

For large arrays, this is too slow.

## Key Insight

Use prefix sums.

Let:

```python
prefix[i]
```

be the sum of elements before index `i`.

Then the sum of subarray `nums[j + 1 ... i]` can be written as:

```python
current_prefix - earlier_prefix
```

At index `i`, suppose the current prefix sum is:

```python
prefix
```

We want a previous prefix sum such that:

```python
prefix - previous = k
```

Rearrange:

```python
previous = prefix - k
```

So for each index, we only need to know whether we have seen prefix sum `prefix - k` before.

If yes, the subarray from after that previous index through current index sums to `k`.

## Why Store the Earliest Index

We want the maximum length.

For the same prefix sum, an earlier index gives a longer subarray.

So we store only the first time each prefix sum appears.

Example:

```python
nums = [1, -1, 5, -2, 3]
k = 3
```

Prefix values:

| Index | Number | Prefix Sum |
|---:|---:|---:|
| before array | none | `0` |
| `0` | `1` | `1` |
| `1` | `-1` | `0` |
| `2` | `5` | `5` |
| `3` | `-2` | `3` |
| `4` | `3` | `6` |

At index `3`, prefix sum is `3`.

We need:

```python
3 - 3 = 0
```

The earliest prefix sum `0` occurred before the array, at index `-1`.

So the subarray length is:

```python
3 - (-1) = 4
```

That gives the answer.

## Algorithm

1. Create a dictionary `first_index`.
2. Store prefix sum `0` at index `-1`.
3. Set `prefix = 0`.
4. Set `answer = 0`.
5. Scan the array from left to right.
6. Add the current number to `prefix`.
7. Compute `need = prefix - k`.
8. If `need` exists in `first_index`, update the answer.
9. If `prefix` has not appeared before, store its current index.
10. Return `answer`.

## Correctness

At index `i`, let `prefix` be the sum of `nums[0]` through `nums[i]`.

A subarray ending at `i` has sum `k` exactly when there exists an earlier prefix sum `need` such that:

```python
prefix - need = k
```

This is equivalent to:

```python
need = prefix - k
```

The algorithm checks exactly this value in the dictionary.

If `need` was first seen at index `j`, then the subarray from `j + 1` through `i` has sum `k`. Its length is:

```python
i - j
```

Because the dictionary stores the earliest index for every prefix sum, this gives the longest valid subarray ending at `i`.

The algorithm checks every possible ending index `i`, so it considers every valid subarray. It keeps the maximum length found.

Therefore, the returned value is the maximum length of any subarray whose sum equals `k`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(n)` | The dictionary may store up to `n + 1` prefix sums |

## Implementation

```python
class Solution:
    def maxSubArrayLen(self, nums: list[int], k: int) -> int:
        first_index = {0: -1}

        prefix = 0
        answer = 0

        for i, num in enumerate(nums):
            prefix += num

            need = prefix - k

            if need in first_index:
                answer = max(answer, i - first_index[need])

            if prefix not in first_index:
                first_index[prefix] = i

        return answer
```

## Code Explanation

We initialize:

```python
first_index = {0: -1}
```

This handles subarrays starting at index `0`.

For example, if `nums[0..i]` sums to `k`, then:

```python
prefix - k = 0
```

and the previous prefix index should be `-1`.

Then we scan the array:

```python
for i, num in enumerate(nums):
    prefix += num
```

At each index, compute the prefix sum needed to form `k`.

```python
need = prefix - k
```

If `need` was seen before, the subarray after that earlier index sums to `k`.

```python
if need in first_index:
    answer = max(answer, i - first_index[need])
```

Then store the current prefix sum only if it has not appeared before.

```python
if prefix not in first_index:
    first_index[prefix] = i
```

This preserves the earliest index and maximizes length.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxSubArrayLen([1, -1, 5, -2, 3], 3) == 4
    assert s.maxSubArrayLen([-2, -1, 2, 1], 1) == 2
    assert s.maxSubArrayLen([1, 2, 3], 7) == 0
    assert s.maxSubArrayLen([1, 2, 3], 6) == 3
    assert s.maxSubArrayLen([0, 0, 0], 0) == 3
    assert s.maxSubArrayLen([2, -2, 2, -2], 0) == 4
    assert s.maxSubArrayLen([-1, 1, -1, 1], 0) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,-1,5,-2,3]`, `3` | Official example |
| `[-2,-1,2,1]`, `1` | Official example with negatives |
| `[1,2,3]`, `7` | No valid subarray |
| `[1,2,3]`, `6` | Whole array is answer |
| `[0,0,0]`, `0` | Many repeated prefix sums |
| `[2,-2,2,-2]`, `0` | Longest zero-sum subarray |
| `[-1,1,-1,1]`, `0` | Negative and positive cancellation |