Domain 2MediumCORE

Maximum Size Subarray Sum Equals k

We are given an array of integers nums and a target integer k. Our goal is to find the length of the longest contiguous subarray (slice) within that array where the elements sum up exactly to k. If no such subarray exists, we return 0.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

325. Maximum Size Subarray Sum Equals k

Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 47.6%


Problem Breakdown

We are given an array of integers nums and a target integer k. Our goal is to find the length of the longest contiguous subarray (slice) within that array where the elements sum up exactly to k. If no such subarray exists, we return 0.

Key Inputs:

  • An integer list nums.
  • A single integer k representing the target sum.

Outputs:

  • An integer representing the maximum length found.

Constraints & Edge Cases:

  • Array size up to 10410^4, which suggests an O(n)O(n) or O(nlog⁡n)O(n \log n) solution is required; O(n2)O(n^2) will likely time out on large inputs in a strict environment like LeetCode’s Python runner for this specific constraint.
  • Elements can be negative, and k can also be negative. This means we cannot use sliding window techniques (which rely on monotonicity). We must handle arbitrary sums via prefix sums.
  • If the subarray starts at index 0, our logic needs to account for a “virtual” sum of 0 existing before any elements are processed.

Intuition

A naive brute-force approach would be to iterate through every possible start and end pair (i,j)(i, j), calculate the sum using slicing or accumulation, and check if it equals k. This is O(n2)O(n^2) for summation checks (or O(1)O(1) with pre-calculation but still nested loops), leading to roughly n3n^3 operations overall. Given N=104N=10^4, this will exceed time limits.

The core insight here relies on the Prefix Sum property: Sum(i,j)=PrefixSum[j]−PrefixSum[i−1]\text{Sum}(i, j) = \text{PrefixSum}[j] - \text{PrefixSum}[i-1] We want Sum(i,j)==k\text{Sum}(i, j) == k. Substituting this into our equation gives us a condition to check at every index jj: PrefixSum[j]−Target=Previous Prefix Sum needed\text{PrefixSum}[j] - \text{Target} = \text{Previous Prefix Sum needed}

As we iterate through the array maintaining a running current_sum, if we encounter a sum that matches (current_sum - k), it implies there exists an earlier subarray ending at i−1i-1 such that subtracting its prefix from our current one yields exactly k. To maximize length, we want to find this previous index as early as possible. Therefore, for any given prefix sum value encountered so far, we only care about the first time it appeared in the array.

Approach

We will use a Hash Map (dictionary) to store the first occurrence of every cumulative prefix sum seen during our traversal. The map key is the prefix_sum and the value is its corresponding index.

  1. Initialize max_len = 0, current_sum = 0.
  2. Create a dictionary seen_sums initialized with {0: -1}. This handles cases where the subarray starts from index 0 (since sum of empty prefix before array is 0 at virtual index -1).
  3. Iterate through nums using an index i. Update current_sum += num.
  4. Check if (current_sum - k) exists in our map:
    • If it does, we found a valid subarray ending at ii. Calculate length as i - seen_sums[current_sum - k] and update max_len.
  5. Store the current sum in the map only if it hasn’t been stored yet (if (current_sum) not in seen_sums). Storing duplicates would overwrite a smaller index with a larger one, which reduces potential subarray lengths for future matches.

Complexity Analysis

  • Time: O(n)O(n) where nn is the length of nums. We traverse the array once. Dictionary lookups and insertions are average O(1)O(1).
  • Space: O(n)O(n) in the worst case, as we might store every unique prefix sum encountered (e.g., if all elements are distinct or sums don’t repeat).

Solution

def maxSubArrayLen(nums: list[int], k: int) -> int:
    # Dictionary to store first occurrence of a specific prefix sum. 
    # Initialize with {0: -1} because a subarray starting at index 0 effectively 
    # subtracts the "prefix sum" before the array started (which is 0).
    seen_sums = {0: -1}
    
    current_sum = 0
    max_len = 0
    
    for i, num in enumerate(nums):
        current_sum += num
        
        # If we have seen a prefix sum such that (current_sum - k) exists, 
        # it means the subarray between that index and now sums to k.
        if (current_sum - k) in seen_sums:
            max_len = max(max_len, i - seen_sums[current_sum - k])
        
        # Only store the sum for the first time we see it. 
        # Storing later occurrences would reduce potential subarray lengths found later.
        if current_sum not in seen_sums:
            seen_sums[current_sum] = i
            
    return max_len

Edge Cases Handled

  • No Subarray Found: If max_len remains 0, the function correctly returns 0 as per requirements.
  • Subarray starting at index 0: The initialization {0: -1} ensures that if a prefix sum equals k, we calculate length from -1 + 1 = i.
  • Negative Numbers/Sum: Since we use a hash map, negative sums are handled correctly as keys.
  • Duplicate Sums: By checking existence before insertion (if current_sum not in seen_sums), we ensure the earliest index is preserved for maximum length calculation.