Maximum Size Subarray Sum Equals k (LeetCode 325)

The problem

Given an integer array nums (values can be negative) and an integer k, return the length of the longest contiguous subarray whose sum is exactly k. If there is none, return 0.

Input:  nums = [1, -1, 5, -2, 3], k = 3
Output: 4

The subarray [1, -1, 5, -2] sums to 3 and has length 4. [3] also sums to 3, but it is shorter.

How to think about it

Start with brute force. Try every start and extend with a running sum, recording the longest that hits k. That is O(n²).

Why not a sliding window? A window works only when all numbers are positive, because then growing the window always increases the sum. Here negatives are allowed, so you cannot tell whether to grow or shrink.

The key insight: a subarray sum is a difference of two prefix sums. The sum of nums[a+1..b] is pre[b] - pre[a]. Setting that equal to k gives pre[a] = pre[b] - k. So at each index b, ask: “did an earlier prefix equal s - k?” If so, the subarray from just after it to here sums to k.

For the longest, keep the earliest index. The length is b - a, so the smallest a wins. Store each prefix sum the first time it appears and never overwrite it. Seed {0: -1} for the empty prefix so a subarray starting at index 0 is measured correctly.

Which pattern is this? Prefix sums plus a hash map. The tell is “longest subarray with sum k” when values can be negative.

Approach

1. Set idx = {0: -1}, s = 0, best = 0.
2. For each index i and value x, add x to s.
3. If s - k is in idx, update best with i - idx[s - k].
4. If s is not yet in idx, record idx[s] = i.
5. Return best.

Solution

def max_subarray_len(nums, k):
    idx = {0: -1}; s = 0; best = 0                # empty prefix at index -1
    for i, x in enumerate(nums):
        s += x
        if s - k in idx: best = max(best, i - idx[s - k])   # earlier prefix equal to s - k
        if s not in idx: idx[s] = i               # keep the earliest index only
    return best
# max_subarray_len([1,-1,5,-2,3], 3) -> 4

Dry run

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

The answer is 4.

Complexity

• Time: O(n). One pass with O(1) average map work per element.
• Space: O(n). Up to one map entry per distinct prefix sum.

Edge cases and pitfalls

• No subarray sums to k returns 0, for example [1, 2] with k = 10.
• k = 0 works with no special case: [1, -1] returns 2 because prefix sum 0 repeats at -1 and 1.
• Overwriting idx[s] with a later index shrinks the span. In the example, prefix sum 0 appears at -1 and again at 1; keeping -1 is what gives length 4.
• Missing {0: -1} loses subarrays that start at index 0, which is exactly the answer here.
• Sliding window gives wrong answers with negative numbers.

Related problems

• Subarray Sum Equals K (LeetCode 560): the same lookup of s - k, but counting matches instead of measuring the longest.
• Contiguous Array (LeetCode 525): this problem with k = 0 after mapping 0 to -1.
• Minimum Size Subarray Sum (LeetCode 209): with only positive numbers, a sliding window works instead.