Maximum Size Subarray Sum Equals k
Medium · Arrays & Hashing · Explanation and code example
Prefix Sums with Earliest Indices
How it works
A subarray ending at i has sum k when an earlier prefix equals currentPrefix - k. Store the earliest index for each prefix, which maximizes the length of any later matching subarray. A zero prefix at index -1 allows subarrays starting at zero.
Steps
- Initialize prefix zero at index -1.
- Update the prefix and look for prefix - k.
- Update the maximum length and store a prefix only on its first occurrence.
Complexity
- Time: O(n) expected with hashing.
- Space: O(n).
Things to watch for
- Do not replace the earliest index for a repeated prefix.
- Negative values make a simple sliding window unsuitable.
- Seed the zero prefix before reading the array.
Python code example
class Solution:
def maxSubArrayLen(self, nums: list[int], k: int) -> int:
ans = 0
prefix = 0
prefixToIndex = {0: -1}
for i, num in enumerate(nums):
prefix += num
target = prefix - k
if target in prefixToIndex:
ans = max(ans, i - prefixToIndex[target])
if prefix not in prefixToIndex:
prefixToIndex[prefix] = i
return ans
C++ code example
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int ans = 0;
int prefix = 0;
unordered_map<int, int> prefixToIndex{{0, -1}};
for (int i = 0; i < nums.size(); ++i) {
prefix += nums[i];
const int target = prefix - k;
if (const auto it = prefixToIndex.find(target);
it != prefixToIndex.cend())
ans = max(ans, i - it->second);
if (!prefixToIndex.contains(prefix))
prefixToIndex[prefix] = i;
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.