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

Function shape:

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

Examples

Example 1:

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

The subarray:

[1, -1, 5, -2]

has sum:

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

Its length is 4.

Output:

4

Example 2:

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

The subarray:

[-1, 2]

has sum:

-1 + 2 = 1

Its length is 2.

Output:

2

Example 3:

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

No subarray sums to 7.

Output:

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.

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:

prefix[i]

be the sum of elements before index i.

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

current_prefix - earlier_prefix

At index i, suppose the current prefix sum is:

prefix

We want a previous prefix sum such that:

prefix - previous = k

Rearrange:

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:

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

Prefix values:

At index 3, prefix sum is 3.

We need:

3 - 3 = 0

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

So the subarray length is:

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:

prefix - need = k

This is equivalent to:

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:

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

Implementation

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:

first_index = {0: -1}

This handles subarrays starting at index 0.

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

prefix - k = 0

and the previous prefix index should be -1.

Then we scan the array:

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

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

need = prefix - k

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

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.

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

This preserves the earliest index and maximizes length.

Testing

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: