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
krepresenting the target sum.
Outputs:
- An integer representing the maximum length found.
Constraints & Edge Cases:
- Array size up to , which suggests an or solution is required; 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
kcan 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 , calculate the sum using slicing or accumulation, and check if it equals k. This is for summation checks (or with pre-calculation but still nested loops), leading to roughly operations overall. Given , this will exceed time limits.
The core insight here relies on the Prefix Sum property: We want . Substituting this into our equation gives us a condition to check at every index :
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 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.
- Initialize
max_len = 0,current_sum = 0. - Create a dictionary
seen_sumsinitialized 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). - Iterate through
numsusing an indexi. Updatecurrent_sum += num. - Check if
(current_sum - k)exists in our map:- If it does, we found a valid subarray ending at . Calculate length as
i - seen_sums[current_sum - k]and updatemax_len.
- If it does, we found a valid subarray ending at . Calculate length as
- 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: where is the length of
nums. We traverse the array once. Dictionary lookups and insertions are average . - Space: 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_lenremains 0, the function correctly returns 0 as per requirements. - Subarray starting at index 0: The initialization
{0: -1}ensures that if a prefix sum equalsk, 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.