NeetCode #152LC-525MediumArrays & Hashing
← Back to All Problems#152 · #525 · Contiguous Array(连续数组)
📌 Problem Statement & Constraints
Given a binary array
nums, return the maximum length of a contiguous subarray with an equal number of 0s and 1s. Constraints: 1 <= nums.length <= 10^5.💡 Core Algorithmic Approaches
- Map
0to-1and keep1as+1. Then a subarray has equal counts exactly when its sum is zero. - A zero-sum subarray corresponds to two equal prefix sums. Store the first index at which each prefix sum appears.
- Sweep once: if the current prefix sum was seen before at index
j, thennums[j..i]is balanced, with lengthi - j. - Keep the earliest occurrence so the length is maximised.
💻 Benchmark Python3 Implementation
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
first = {0: -1} # prefix sum -> earliest index
cur = 0
best = 0
for i, x in enumerate(nums):
cur += 1 if x == 1 else -1 # map 0 -> -1
if cur in first:
best = max(best, i - first[cur])
else:
first[cur] = i # keep only the earliest
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with O(1) average hash operations.
💾 Space Complexity
O(n) for the prefix-sum map.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting
first[0] = -1: a balanced prefix starting at index 0 would be missed. - Overwriting
first[cur]: keeping the latest index minimises the length; only the earliest should be stored. - Treating this as a sliding window: it fails because the prefix sum is not monotone in a way that lets you shrink greedily -- the map approach is the right tool.
- Mapping
0to0instead of-1: then a balanced subarray would not have sum zero.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.