Problem Description

You are given an integer array nums and an integer k. Your task is to find the maximum length of a contiguous subarray whose elements sum to exactly k. If no such subarray exists, return 0.

A subarray is a contiguous sequence of elements within an array. For example, in the array [1, 2, 3, 4], some subarrays include [1, 2], [2, 3, 4], and [3], but [1, 3] is not a subarray because the elements are not contiguous.

The problem asks you to:

1. Find all possible contiguous subarrays of nums
2. Check which ones have a sum equal to k
3. Return the length of the longest such subarray
4. If no subarray sums to k, return 0

For example:

• If nums = [1, -1, 5, -2, 3] and k = 3, the subarray [1, -1, 5, -2] sums to 3 and has length 4, which would be the answer.
• If nums = [2, 3, 4] and k = 10, no subarray sums to 10, so the answer would be 0.

Intuition

The naive approach would be to check all possible subarrays and find the longest one with sum k. However, this would require O(n²) or O(n³) time complexity, which is inefficient for large arrays.

The key insight is to use prefix sums. If we know the cumulative sum up to each position, we can calculate any subarray sum quickly. Specifically, if we have the prefix sum at position i as s, and we want a subarray ending at position i with sum k, then we need to find if there exists a position j where the prefix sum was s - k.

Why does this work? Because the subarray from position j+1 to i would have sum = (prefix sum at i) - (prefix sum at j) = s - (s - k) = k.

To implement this efficiently, we can use a hash table to store the first occurrence of each prefix sum value. As we iterate through the array:

• We calculate the running prefix sum s
• We check if s - k exists in our hash table
• If it does, we've found a subarray with sum k, and we can calculate its length
• We store the current prefix sum s with its index if it hasn't been seen before

The reason we only store the first occurrence of each prefix sum is crucial: if the same prefix sum appears multiple times, using the earliest occurrence gives us the longest possible subarray ending at the current position.

We initialize the hash table with {0: -1} to handle the case where the subarray starts from index 0. This way, if the prefix sum equals k exactly, we can correctly calculate the length as i - (-1) = i + 1.

Solution Approach

We implement the solution using a hash table and prefix sum technique:

1. Initialize the hash table: Create a dictionary d with initial value {0: -1}. This handles the case where a subarray starting from index 0 has sum equal to k.

2. Initialize tracking variables:

   • ans = 0: Tracks the maximum length found so far
   • s = 0: Maintains the running prefix sum

3. Iterate through the array: For each element at index i with value x:

   a. Update prefix sum: Add the current element to the running sum: s += x

   b. Check for valid subarray: If s - k exists in the hash table d, it means we've found a subarray with sum k:

   • The subarray spans from index d[s - k] + 1 to index i
   • Its length is i - d[s - k]
   • Update ans with the maximum of current ans and this new length: ans = max(ans, i - d[s - k])

   c. Store prefix sum: If the current prefix sum s hasn't been seen before (not in d), store it with its index: d[s] = i

   • We only store the first occurrence to maximize potential subarray lengths
   • If s already exists in d, we don't update it because keeping the earlier index gives us longer subarrays

4. Return the result: After processing all elements, return ans which contains the maximum length found.

The algorithm runs in O(n) time complexity with a single pass through the array, and uses O(n) space complexity for the hash table in the worst case where all prefix sums are unique.

Example Walkthrough

Let's walk through the solution with nums = [1, -1, 5, -2, 3] and k = 3.

We'll track the prefix sum s, our hash table d, and the maximum length ans.

Initial state:

• d = {0: -1} (handles subarrays starting from index 0)
• s = 0 (running prefix sum)
• ans = 0 (maximum length found)

Step 1: Process nums[0] = 1 (i = 0)

• Update prefix sum: s = 0 + 1 = 1
• Check if s - k = 1 - 3 = -2 exists in d: No
• Store prefix sum: d[1] = 0, so d = {0: -1, 1: 0}
• Current ans = 0

Step 2: Process nums[1] = -1 (i = 1)

• Update prefix sum: s = 1 + (-1) = 0
• Check if s - k = 0 - 3 = -3 exists in d: No
• Check if s = 0 exists in d: Yes! It's already there (from initialization)
  • We don't update d[0] because we keep the first occurrence
• So d = {0: -1, 1: 0}
• Current ans = 0

Step 3: Process nums[2] = 5 (i = 2)

• Update prefix sum: s = 0 + 5 = 5
• Check if s - k = 5 - 3 = 2 exists in d: No
• Store prefix sum: d[5] = 2, so d = {0: -1, 1: 0, 5: 2}
• Current ans = 0

Step 4: Process nums[3] = -2 (i = 3)

• Update prefix sum: s = 5 + (-2) = 3
• Check if s - k = 3 - 3 = 0 exists in d: Yes! d[0] = -1
  • Found a subarray from index (-1) + 1 = 0 to index 3
  • Length = 3 - (-1) = 4
  • Update ans = max(0, 4) = 4
• Store prefix sum: d[3] = 3, so d = {0: -1, 1: 0, 5: 2, 3: 3}
• Current ans = 4

Step 5: Process nums[4] = 3 (i = 4)

• Update prefix sum: s = 3 + 3 = 6
• Check if s - k = 6 - 3 = 3 exists in d: Yes! d[3] = 3
  • Found a subarray from index 3 + 1 = 4 to index 4
  • Length = 4 - 3 = 1
  • Update ans = max(4, 1) = 4
• Store prefix sum: d[6] = 4, so d = {0: -1, 1: 0, 5: 2, 3: 3, 6: 4}
• Current ans = 4

Result: The maximum length is 4, corresponding to the subarray [1, -1, 5, -2] which sums to 3.

The key insight: When we reached index 3 with prefix sum 3, we found that prefix sum 0 existed at index -1. This means the subarray from index 0 to 3 has sum = 3 - 0 = 3, giving us our answer.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once using the enumerate function, and for each element, it performs constant-time operations: calculating the cumulative sum, checking if s - k exists in the dictionary, updating the maximum length, and potentially adding a new entry to the dictionary. Dictionary operations (lookup and insertion) are O(1) on average.

The space complexity is O(n), where n is the length of the array nums. In the worst case, when all cumulative sum values are unique, the dictionary d will store up to n + 1 entries (including the initial entry {0: -1} plus one entry for each element in the array). The remaining variables (ans, s, i, x) use constant space.

Common Pitfalls

Pitfall 1: Overwriting Earlier Prefix Sum Indices

The Problem: A critical mistake is updating the hash table every time we encounter a prefix sum, even if we've seen it before:

# WRONG approach
for current_index, num in enumerate(nums):
    cumulative_sum += num
  
    if cumulative_sum - k in sum_to_index:
        subarray_length = current_index - sum_to_index[cumulative_sum - k]
        max_length = max(max_length, subarray_length)
  
    # This overwrites earlier occurrences - MISTAKE!
    sum_to_index[cumulative_sum] = current_index  

Why it's wrong: When we overwrite an earlier index with a later one, we lose the opportunity to find longer subarrays. For example, with nums = [1, 1, 0] and k = 1:

• At index 0: cumulative_sum = 1, store {1: 0}
• At index 1: cumulative_sum = 2, check for sum 1 (found at index 0), length = 1
• At index 2: cumulative_sum = 2 again
  • If we overwrite: {2: 2} replaces {2: 1}
  • This prevents us from finding longer subarrays later

The Solution: Only store the first occurrence of each prefix sum:

# CORRECT approach
if cumulative_sum not in sum_to_index:
    sum_to_index[cumulative_sum] = current_index

Pitfall 2: Forgetting the Base Case

The Problem: Not initializing the hash table with {0: -1}:

# WRONG - missing base case
sum_to_index = {}  # Should be {0: -1}

Why it's wrong: This misses subarrays that start from index 0. For example, with nums = [1, 2] and k = 3:

• The entire array sums to 3, but without the base case, we can't detect it
• We need {0: -1} to handle when cumulative_sum == k

The Solution: Always initialize with the base case:

sum_to_index = {0: -1}

Pitfall 3: Incorrect Length Calculation

The Problem: Using the wrong formula for calculating subarray length:

# WRONG calculations
subarray_length = current_index - sum_to_index[target_sum] - 1  # Too short
subarray_length = current_index - sum_to_index[target_sum] + 1  # Too long

Why it's wrong: The subarray spans from sum_to_index[target_sum] + 1 to current_index inclusive. The correct length is the difference between these indices.

The Solution: Use the correct formula:

subarray_length = current_index - sum_to_index[target_sum]

Example Demonstrating All Fixes:

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

With correct implementation:

1. Initialize: {0: -1}, max_length = 0, sum = 0
2. Index 0 (val=1): sum = 1, check for -2 (not found), store {0: -1, 1: 0}
3. Index 1 (val=-1): sum = 0, check for -3 (not found), 0 already exists (don't overwrite)
4. Index 2 (val=5): sum = 5, check for 2 (not found), store {0: -1, 1: 0, 5: 2}
5. Index 3 (val=-2): sum = 3, check for 0 (found at -1), length = 3 - (-1) = 4
6. Index 4 (val=3): sum = 6, check for 3 (not found), store {0: -1, 1: 0, 5: 2, 3: 3, 6: 4}

Result: Maximum length = 4 (subarray [1, -1, 5, -2])