⚡Flashcard Drill➔
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

  1. Map 0 to -1 and keep 1 as +1. Then a subarray has equal counts exactly when its sum is zero.
  2. A zero-sum subarray corresponds to two equal prefix sums. Store the first index at which each prefix sum appears.
  3. Sweep once: if the current prefix sum was seen before at index j, then nums[j..i] is balanced, with length i - j.
  4. 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 0 to 0 instead 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems