51. Contiguous Array

🔗 LeetCode Problem: 525. Contiguous Array
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Prefix Sum

Problem Statement

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] or [1, 0] are the longest contiguous subarrays with equal number of 0 and 1.

Constraints: - 1 <= nums.length <= 10^5 - nums[i] is either 0 or 1.

🎨 Visual Understanding

The Problem Visualized

nums = [0, 1, 0, 1, 1, 0]

Check subarrays:
[0, 1] → 1 zero, 1 one → length 2 ✓
[0, 1, 0, 1] → 2 zeros, 2 ones → length 4 ✓
[1, 0, 1, 1, 0] → 2 zeros, 3 ones → not equal ✗
[0, 1, 0, 1, 1, 0] → 3 zeros, 3 ones → length 6 ✓

Maximum length: 6

Key Observation: Transform to Balance Problem

🚨 CRITICAL INSIGHT - Read This Carefully!

Instead of tracking 0s and 1s separately,
treat 0 as -1 and 1 as +1.

Equal number of 0s and 1s means sum = 0!

Original: [0, 1, 0, 1, 1, 0]
Transform: [-1, 1, -1, 1, 1, -1]

Find subarray with sum = 0:
  [-1, 1] → sum = 0 ✓
  [-1, 1, -1, 1] → sum = 0 ✓
  [-1, 1, -1, 1, 1, -1] → sum = 0 ✓

🚨 CRITICAL: Why Check for SAME Balance (Not Just Balance = 0)?

This is the key insight many people miss!

Question: "Why check if balance[i] == balance[j]? 
           Can't I just check if balance = 0?"

Answer: NO! Checking only balance = 0 will MISS many valid subarrays!

Case 1: Balanced subarray STARTING from index 0

nums = [0, 1, 0, 1]
Transform: [-1, +1, -1, +1]

Index:  0   1   2   3
Balance: -1  0  -1  0
             ↑       ↑
           Zero!   Zero!

Balance = 0 means:
  Subarray from START (index 0) to current is balanced!

Index 1: [0,1] from 0-1 has 1 zero, 1 one ✓
Index 3: [0,1,0,1] from 0-3 has 2 zeros, 2 ones ✓

✅ For subarrays starting at 0: YES, balance = 0 works!

Case 2: Balanced subarray NOT starting from index 0

nums = [1, 1, 1, 0, 0]
Transform: [+1, +1, +1, -1, -1]

Index:  0   1   2   3   4
Balance: +1 +2 +3 +2 +1
                 ↑  ↑
              Same balance = +2!

Balance NEVER equals 0!

If we ONLY check balance = 0:
  Result: 0 (no balanced subarray found) ✗ WRONG!

But if we check for SAME balance:
  balance = +2 at indices 1 and 3
  Subarray from index 2 to 3: [1, 0]
  Has 1 one and 1 zero ✓
  Length: 3 - 1 = 2

  balance = +1 at indices 0 and 4
  Subarray from index 1 to 4: [1, 1, 0, 0]
  Has 2 ones and 2 zeros ✓
  Length: 4 - 0 = 4 ✓

Maximum length: 4 ✓

❌ If we only checked balance = 0, we'd return 0 (completely wrong)!

The Mathematical Reason:

If balance[j] == balance[i]:

Then:
  balance[j] = sum from index 0 to j
  balance[i] = sum from index 0 to i

Subarray sum from i+1 to j:
  = balance[j] - balance[i]
  = balance[j] - balance[j]  (same value!)
  = 0 ✓

Sum = 0 means equal 0s and 1s!

Visual Proof:

nums = [1, 0, 1, 1, 0, 0]
       [+1, -1, +1, +1, -1, -1]

Index:  0   1   2   3   4   5
Balance: +1  0  +1 +2 +1  0
         ↑   ↑  ↑      ↑  ↑
         │   │  └──────┘  │
         │   └────────────┘
         Same!  Same!   Same!

Balance +1 appears at: 0, 2, 4
  Indices 0 to 2: sum = balance[2] - balance[0] = +1 - (+1) = 0
    Subarray [0, 1] from index 1-2 (1 zero, 1 one) ✓

  Indices 2 to 4: sum = balance[4] - balance[2] = +1 - (+1) = 0
    Subarray [1, 0] from index 3-4 (1 one, 1 zero) ✓

  Indices 0 to 4: sum = balance[4] - balance[0] = +1 - (+1) = 0
    Subarray [0, 1, 1, 0] from index 1-4 (2 zeros, 2 ones) ✓

Balance 0 appears at: 1, 5
  Indices 1 to 5: [1, 1, 0, 0] from index 2-5 (2 zeros, 2 ones) ✓

Summary Table:

What to Check	What It Finds	Can Miss?
balance = 0 ONLY	Subarrays starting from index 0	❌ YES - Misses middle subarrays!
balance[i] = balance[j]	ALL balanced subarrays	✅ NO - Finds everything!

Key Takeaway:

✓ Check if CURRENT balance exists in HashMap
✓ This handles BOTH:
  1. Balance = 0 (subarray from start)
  2. Balance = any repeated value (subarray anywhere)

Using HashMap with {0: -1} initialization handles ALL cases!

The Insight: Use Running Balance (Revised)

nums = [0, 1, 0, 1, 1, 0]
Transform to: [-1, 1, -1, 1, 1, -1]

Calculate running balance:
Index:   -1   0   1   2   3   4   5
Value:        -1  1  -1  1   1  -1
Balance:  0  -1   0  -1  0   1   0
          ↑       ↑       ↑       ↑
        Same balance = 0!

Balance 0 appears at: -1, 1, 3, 5
Balance -1 appears at: 0, 2

When balance repeats:
  The subarray between has sum = 0!
  Equal number of 0s and 1s!

All valid subarrays:
  Indices -1 to 1: [0,1] length 2
  Indices 0 to 2: [1,0] length 2  
  Indices -1 to 3: [0,1,0,1] length 4
  Indices 2 to 3: not applicable (same index check)
  Indices -1 to 5: [0,1,0,1,1,0] length 6 ✓ Maximum!

Longest distance: 5 - (-1) = 6
Subarray: entire array [0,1,0,1,1,0]

Why This Works

If balance[j] == balance[i]:

Then:
  balance[j] = sum from 0 to j
  balance[i] = sum from 0 to i

  sum(i+1 to j) = balance[j] - balance[i]
                = balance[j] - balance[j]  (same balance)
                = 0

Sum = 0 means equal 0s and 1s! ✓

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all subarrays:
1. For each starting position i
2. For each ending position j
3. Count 0s and 1s in subarray [i, j]
4. If equal, update max length

Implementation

public int findMaxLength(int[] nums) {
    int maxLen = 0;

    for (int i = 0; i < nums.length; i++) {
        int zeros = 0, ones = 0;
        for (int j = i; j < nums.length; j++) {
            if (nums[j] == 0) {
                zeros++;
            } else {
                ones++;
            }

            if (zeros == ones) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }

    return maxLen;
}

⏰ Time: O(n²) - nested loops
💾 Space: O(1) - only variables

🎯 Approach 2: Prefix Sum Array

Better Approach 💡

Core Logic:

Transform problem:
1. Replace 0 with -1 (keep 1 as +1)
2. Build prefix sum array
3. Find pairs with same prefix sum
4. Distance between pairs = length of balanced subarray

Key insight:
  If prefixSum[j] == prefixSum[i]
  Then sum(i+1 to j) = 0
  Which means equal 0s and 1s!

Visual Explanation:

nums = [0, 1, 0, 1, 1, 0]
Transform: [-1, 1, -1, 1, 1, -1]

Build prefix sum:
Index:    -1   0   1   2   3   4   5
Prefix:    0  -1   0  -1   0   1   0

Find duplicate prefix sums:
  Prefix sum 0 at: -1, 1, 3, 5
  Prefix sum -1 at: 0, 2

Longest distance for prefix sum 0:
  5 - (-1) = 6

Subarray: indices 0 to 5 (entire array)

Implementation

public int findMaxLength(int[] nums) {
    int n = nums.length;

    // Build prefix sum array (treat 0 as -1)
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        int value = (nums[i] == 0) ? -1 : 1;
        prefixSum[i + 1] = prefixSum[i] + value;
    }

    int maxLen = 0;

    // Check all pairs with same prefix sum
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (prefixSum[i] == prefixSum[j]) {
                maxLen = Math.max(maxLen, j - i);
            }
        }
    }

    return maxLen;
}

⏰ Time: O(n²) - checking all pairs
💾 Space: O(n) - prefix sum array

✅ Approach 3: HashMap with Running Balance (Optimal)

The Ultimate Optimization 💡

Core Logic:

Use HashMap to track first occurrence of each balance:

Key insight:
  Treat 0 as -1, 1 as +1
  Track running balance (cumulative sum)
  When same balance seen again:
    - Subarray between has balance 0
    - Equal number of 0s and 1s!

Algorithm:
1. Initialize map with {0: -1}
2. Track running balance
3. If balance seen before:
   - Calculate length: current_index - first_index
   - Update max length
4. If new balance: store it

Visual Explanation:

nums = [0, 1, 0, 1, 1, 0]

Running balance (0→-1, 1→+1):
Index: -1   0   1   2   3   4   5
Value:     -1  +1  -1  +1  +1  -1
Balance: 0 -1   0  -1   0  +1   0
         ↑      ↑       ↑        ↑
       Initial  │       │        │
              Same    Same     Same

Map evolution:
  map = {0: -1}

  i=0: balance=-1, NEW → map = {0: -1, -1: 0}
  i=1: balance=0, SEEN at -1 → length = 1-(-1) = 2
  i=2: balance=-1, SEEN at 0 → length = 2-0 = 2
  i=3: balance=0, SEEN at -1 → length = 3-(-1) = 4
  i=4: balance=1, NEW → map = {0: -1, -1: 0, 1: 4}
  i=5: balance=0, SEEN at -1 → length = 5-(-1) = 6 ✓

Maximum length: 6

Why Store Index -1 for Balance 0?

Edge case: Balanced prefix from start

nums = [0, 1]
Transform: [-1, +1]

i=0: balance=-1, map = {0: -1, -1: 0}
i=1: balance=0, FOUND at -1!
     length = 1 - (-1) = 2 ✓

Without {0: -1}:
  We'd miss this case!

Implementation

public int findMaxLength(int[] nums) {
    // Map: balance -> first index where this balance was seen
    Map<Integer, Integer> map = new HashMap<>();

    // Initialize: balance 0 at index -1
    // Handles case where prefix from start is balanced
    map.put(0, -1);

    int balance = 0;
    int maxLen = 0;

    for (int i = 0; i < nums.length; i++) {
        // Treat 0 as -1, 1 as +1
        balance += (nums[i] == 0) ? -1 : 1;

        if (map.containsKey(balance)) {
            // Found same balance before
            int length = i - map.get(balance);
            maxLen = Math.max(maxLen, length);
        } else {
            // First time seeing this balance
            map.put(balance, i);
        }
    }

    return maxLen;
}

⏰ Time: O(n) - single pass
💾 Space: O(n) - hashmap stores at most n+1 different balances

🔍 Step-by-Step Execution

Approach 2 (Prefix Sum Array): nums = [1, 1, 1, 0, 0]

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 1, 1, 0, 0]
n = 5


STEP 1: Build Prefix Sum Array (Transform 0→-1, 1→+1)
═══════════════════════════════════════════════════════════════════

prefixSum[0] = 0 (initial)

i=0: nums[0] = 1 → value = +1
  prefixSum[1] = 0 + 1 = 1

i=1: nums[1] = 1 → value = +1
  prefixSum[2] = 1 + 1 = 2

i=2: nums[2] = 1 → value = +1
  prefixSum[3] = 2 + 1 = 3

i=3: nums[3] = 0 → value = -1
  prefixSum[4] = 3 + (-1) = 2

i=4: nums[4] = 0 → value = -1
  prefixSum[5] = 2 + (-1) = 1

Final prefixSum array:
  Index:  0  1  2  3  4  5
  Prefix: 0  1  2  3  2  1


STEP 2: Find Pairs with Same Prefix Sum
═══════════════════════════════════════════════════════════════════

Check all pairs (i, j) where j > i:

i=0: prefixSum[0] = 0
───────────────────────────────────────────────────────────────────
  j=1: prefixSum[1] = 1, 0 ≠ 1 ✗
  j=2: prefixSum[2] = 2, 0 ≠ 2 ✗
  j=3: prefixSum[3] = 3, 0 ≠ 3 ✗
  j=4: prefixSum[4] = 2, 0 ≠ 2 ✗
  j=5: prefixSum[5] = 1, 0 ≠ 1 ✗

i=1: prefixSum[1] = 1
───────────────────────────────────────────────────────────────────
  j=2: prefixSum[2] = 2, 1 ≠ 2 ✗
  j=3: prefixSum[3] = 3, 1 ≠ 3 ✗
  j=4: prefixSum[4] = 2, 1 ≠ 2 ✗
  j=5: prefixSum[5] = 1, 1 = 1 ✓ MATCH!

  Length = 5 - 1 = 4
  maxLen = max(0, 4) = 4

  Subarray: indices 2 to 5 → [1, 1, 0, 0]
  Verification: 2 ones, 2 zeros ✓

i=2: prefixSum[2] = 2
───────────────────────────────────────────────────────────────────
  j=3: prefixSum[3] = 3, 2 ≠ 3 ✗
  j=4: prefixSum[4] = 2, 2 = 2 ✓ MATCH!

  Length = 4 - 2 = 2
  maxLen = max(4, 2) = 4

  Subarray: indices 3 to 4 → [1, 0]
  Verification: 1 one, 1 zero ✓

i=3: prefixSum[3] = 3
───────────────────────────────────────────────────────────────────
  j=4: prefixSum[4] = 2, 3 ≠ 2 ✗
  j=5: prefixSum[5] = 1, 3 ≠ 1 ✗

i=4: prefixSum[4] = 2
───────────────────────────────────────────────────────────────────
  j=5: prefixSum[5] = 1, 2 ≠ 1 ✗


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: maxLen = 4
═══════════════════════════════════════════════════════════════════

Best subarray: [1, 1, 0, 0] from indices 2-5
Has 2 ones and 2 zeros ✓

Key Insight Demonstrated:
  Balance NEVER equals 0 in this example!
  If we only checked balance = 0, we'd get 0 (wrong!)
  But by checking for SAME balance, we found length 4 ✓

Approach 3 (HashMap): nums = [0, 1, 0, 1, 1, 0]

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 1, 0, 1, 1, 0]
n = 6
map = {0: -1}
balance = 0
maxLen = 0


Index 0: nums[0] = 0 (treat as -1)
═══════════════════════════════════════════════════════════════════
balance = 0 + (-1) = -1

Check map for balance -1: NOT found

Add to map:
  map = {0: -1, -1: 0}

maxLen = 0


Index 1: nums[1] = 1 (treat as +1)
═══════════════════════════════════════════════════════════════════
balance = -1 + 1 = 0

Check map for balance 0: FOUND at index -1!

Calculate length:
  length = 1 - (-1) = 2

Update maxLen:
  maxLen = max(0, 2) = 2

Don't update map (keep first occurrence):
  map = {0: -1, -1: 0}

Subarray [0, 1]: 1 zero, 1 one ✓


Index 2: nums[2] = 0 (treat as -1)
═══════════════════════════════════════════════════════════════════
balance = 0 + (-1) = -1

Check map for balance -1: FOUND at index 0!

Calculate length:
  length = 2 - 0 = 2

Update maxLen:
  maxLen = max(2, 2) = 2

map = {0: -1, -1: 0}

Subarray from index 1 to 2: [1, 0] → 1 zero, 1 one ✓


Index 3: nums[3] = 1 (treat as +1)
═══════════════════════════════════════════════════════════════════
balance = -1 + 1 = 0

Check map for balance 0: FOUND at index -1!

Calculate length:
  length = 3 - (-1) = 4

Update maxLen:
  maxLen = max(2, 4) = 4

map = {0: -1, -1: 0}

Subarray from index 0 to 3: [0,1,0,1] → 2 zeros, 2 ones ✓


Index 4: nums[4] = 1 (treat as +1)
═══════════════════════════════════════════════════════════════════
balance = 0 + 1 = 1

Check map for balance 1: NOT found

Add to map:
  map = {0: -1, -1: 0, 1: 4}

maxLen = 4


Index 5: nums[5] = 0 (treat as -1)
═══════════════════════════════════════════════════════════════════
balance = 1 + (-1) = 0

Check map for balance 0: FOUND at index -1!

Calculate length:
  length = 5 - (-1) = 6

Update maxLen:
  maxLen = max(4, 6) = 6

map = {0: -1, -1: 0, 1: 4}

Subarray from index 0 to 5: [0,1,0,1,1,0] → 3 zeros, 3 ones ✓


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 6
═══════════════════════════════════════════════════════════════════

The entire array has equal 0s and 1s!

Example 2: nums = [0, 1, 0]

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 1, 0]
map = {0: -1}
balance = 0
maxLen = 0


Index 0: nums[0] = 0
═══════════════════════════════════════════════════════════════════
balance = -1
map = {0: -1, -1: 0}


Index 1: nums[1] = 1
═══════════════════════════════════════════════════════════════════
balance = 0
Found at -1!
length = 1 - (-1) = 2
maxLen = 2
map = {0: -1, -1: 0}


Index 2: nums[2] = 0
═══════════════════════════════════════════════════════════════════
balance = -1
Found at 0!
length = 2 - 0 = 2
maxLen = max(2, 2) = 2
map = {0: -1, -1: 0}


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 2
═══════════════════════════════════════════════════════════════════

Two valid subarrays of length 2:
  [0, 1] at indices 0-1
  [1, 0] at indices 1-2

Example 3 (CRITICAL): nums = [1, 1, 1, 0, 0]

This example demonstrates WHY we need to check for same balance, not just balance = 0!

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 1, 1, 0, 0]
map = {0: -1}
balance = 0
maxLen = 0

IMPORTANT: Watch how balance NEVER returns to 0!


Index 0: nums[0] = 1 (treat as +1)
═══════════════════════════════════════════════════════════════════
balance = 0 + 1 = 1

Check map for balance 1: NOT found

Add to map:
  map = {0: -1, 1: 0}

maxLen = 0


Index 1: nums[1] = 1 (treat as +1)
═══════════════════════════════════════════════════════════════════
balance = 1 + 1 = 2

Check map for balance 2: NOT found

Add to map:
  map = {0: -1, 1: 0, 2: 1}

maxLen = 0


Index 2: nums[2] = 1 (treat as +1)
═══════════════════════════════════════════════════════════════════
balance = 2 + 1 = 3

Check map for balance 3: NOT found

Add to map:
  map = {0: -1, 1: 0, 2: 1, 3: 2}

maxLen = 0


Index 3: nums[3] = 0 (treat as -1)
═══════════════════════════════════════════════════════════════════
balance = 3 + (-1) = 2

Check map for balance 2: FOUND at index 1! ✓

Calculate length:
  length = 3 - 1 = 2

Update maxLen:
  maxLen = max(0, 2) = 2

Don't update map (keep first occurrence):
  map = {0: -1, 1: 0, 2: 1, 3: 2}

Subarray from index 2 to 3: [1, 0]
Verification: 1 one, 1 zero ✓

🔑 KEY INSIGHT: Balance = 2 (not 0), but SAME as before!
   This means subarray sum = 0!


Index 4: nums[4] = 0 (treat as -1)
═══════════════════════════════════════════════════════════════════
balance = 2 + (-1) = 1

Check map for balance 1: FOUND at index 0! ✓

Calculate length:
  length = 4 - 0 = 4

Update maxLen:
  maxLen = max(2, 4) = 4

map = {0: -1, 1: 0, 2: 1, 3: 2}

Subarray from index 1 to 4: [1, 1, 0, 0]
Verification: 2 ones, 2 zeros ✓

🔑 KEY INSIGHT: Balance = 1 (not 0), but SAME as at index 0!
   This means subarray sum = 0!


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 4
═══════════════════════════════════════════════════════════════════

Best subarray: [1, 1, 0, 0] from indices 1-4
Has 2 ones and 2 zeros ✓

🚨 CRITICAL OBSERVATION:
═══════════════════════════════════════════════════════════════════

Balance values seen: 1, 2, 3, 2, 1

Balance NEVER equals 0!

If we ONLY checked for balance = 0:
  We would return maxLen = 0 ✗ COMPLETELY WRONG!

But by checking if balance exists in HashMap:
  We found matching balances (2 at indices 1,3 and 1 at indices 0,4)
  We correctly returned maxLen = 4 ✓

This is WHY we check map.containsKey(balance) instead of just balance == 0!

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 1, 0]
map = {0: -1}
balance = 0
maxLen = 0


Index 0: nums[0] = 0
═══════════════════════════════════════════════════════════════════
balance = -1
map = {0: -1, -1: 0}


Index 1: nums[1] = 1
═══════════════════════════════════════════════════════════════════
balance = 0
Found at -1!
length = 1 - (-1) = 2
maxLen = 2
map = {0: -1, -1: 0}


Index 2: nums[2] = 0
═══════════════════════════════════════════════════════════════════
balance = -1
Found at 0!
length = 2 - 0 = 2
maxLen = max(2, 2) = 2
map = {0: -1, -1: 0}


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 2
═══════════════════════════════════════════════════════════════════

Two valid subarrays of length 2:
  [0, 1] at indices 0-1
  [1, 0] at indices 1-2

🔍 Edge Cases

Case 1: All zeros
Input: nums = [0, 0, 0]
Output: 0
Explanation: No way to have equal 0s and 1s

Case 2: All ones
Input: nums = [1, 1, 1]
Output: 0
Explanation: No way to have equal 0s and 1s

Case 3: Single pair
Input: nums = [0, 1]
Output: 2
Explanation: Entire array is balanced

Case 4: Entire array balanced
Input: nums = [0, 1, 0, 1, 1, 0]
Output: 6

Case 5: No balanced subarray
Input: nums = [0, 0, 1]
Output: 2
Explanation: [0, 1] at indices 1-2

Case 6: Multiple balanced subarrays
Input: nums = [0, 1, 0, 1]
Output: 4
Explanation: Entire array

Case 7: Balanced at start
Input: nums = [0, 1, 1, 0, 1]
Output: 4
Explanation: [0, 1, 1, 0]

Case 8: Balanced at end
Input: nums = [1, 0, 1, 0, 1]
Output: 4
Explanation: [0, 1, 0, 1]

Case 9: Long array with small balance
Input: nums = [0, 0, 1, 0, 0, 0, 1, 1]
Output: 6
Explanation: [0, 1, 0, 0, 0, 1] has 4 zeros and 2 ones... 
Actually [0, 0, 1, 0, 0, 0, 1, 1] at indices 1-8 
has 4 zeros and 2 ones... Let me recalculate:
[0, 1, 0, 0, 0, 1] → 4 zeros, 2 ones ✗
[1, 0, 0, 0, 1, 1] → 3 zeros, 3 ones ✓ (length 6)

Common Mistakes

Mistake 1: Not initializing map with {0: -1}
❌ Wrong: 
    Map<Integer, Integer> map = new HashMap<>();
    // Missing initialization
✓ Right: 
    map.put(0, -1);
Reason: Handles balanced prefix from start

Mistake 2: Treating 0 and 1 directly instead of -1 and +1
❌ Wrong: 
    balance += nums[i];  // Adding 0 or 1
✓ Right: 
    balance += (nums[i] == 0) ? -1 : 1;
Reason: Need sum to be 0 for equal count

Mistake 3: Updating existing balance in map
❌ Wrong: 
    map.put(balance, i);  // Always update
✓ Right: 
    if (!map.containsKey(balance)) {
        map.put(balance, i);
    }
Reason: Want earliest occurrence to maximize length

Mistake 4: Wrong length calculation
❌ Wrong: 
    int length = i - map.get(balance) + 1;
    // Off by one!
✓ Right: 
    int length = i - map.get(balance);
Reason: Distance between indices, not including first

Mistake 5: Counting 0s and 1s separately
❌ Wrong: 
    int zeros = 0, ones = 0;
    // Track separately, compare at end
✓ Right: 
    int balance = 0;
    // Use balance, check when same
Reason: Balance approach is more efficient

Mistake 6: Not maximizing length
❌ Wrong: 
    if (map.containsKey(balance)) {
        return i - map.get(balance);
        // Return immediately
    }
✓ Right: 
    if (map.containsKey(balance)) {
        maxLen = Math.max(maxLen, i - map.get(balance));
        // Keep checking for longer
    }
Reason: Need to find MAXIMUM length, not first match

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

  Count 0s and 1s for each subarray

Approach 2: Prefix Sum Array
  Time: O(n²)
  Space: O(n)
  Use: Learning step

  Build prefix sum, find pairs with same sum
  Better understanding of the transformation

Approach 3: HashMap (RECOMMENDED)
  Time: O(n)
  Space: O(n)
  Use: Optimal solution

  Track balance with HashMap
  Single pass, O(1) lookups

🔑 The Core Insight

🚨 MOST IMPORTANT CONCEPT - Don't Miss This!
═══════════════════════════════════════════════════════════════

Problem Transformation:
───────────────────────────────────────────────────────────────

Original problem:
  Find longest subarray with equal 0s and 1s

Transform:
  Treat 0 as -1, keep 1 as +1
  Find longest subarray with sum = 0

Why this works:
  Equal 0s and 1s means:
    count(0) = count(1)
    count(-1) + count(+1) = 0
    sum = 0 ✓


🚨 CRITICAL: Why NOT Just Check Balance = 0?
═══════════════════════════════════════════════════════════════

Many people think: "Just check if balance equals 0!"

This is WRONG and will fail many test cases!

Example that breaks "check balance = 0 only":
  nums = [1, 1, 1, 0, 0]
  Transform: [+1, +1, +1, -1, -1]

  Balance: +1, +2, +3, +2, +1

  Balance NEVER equals 0!

  If checking only balance = 0: return 0 ✗ WRONG!

  But [1, 1, 0, 0] is valid (2 ones, 2 zeros)!
  Balance +1 at indices 0 and 4 → length 4 ✓


The Mathematical Truth:
═══════════════════════════════════════════════════════════════

If balance[j] == balance[i]:
  Then sum(i+1 to j) = balance[j] - balance[i] = 0 ✓

This works for ANY balance value:
  - balance = 0 (subarray from start)
  - balance = 5 (subarray in middle)  
  - balance = -3 (subarray anywhere)

As long as balance REPEATS, subarray between is balanced!


Balance Concept:
═══════════════════════════════════════════════════════════════

Running balance = cumulative sum

When balance repeats:
  balance[j] = balance[i]

Then:
  sum(i+1 to j) = balance[j] - balance[i]
                = same - same
                = 0 ✓

Which means equal 0s and 1s!


What to Check:
═══════════════════════════════════════════════════════════════

✗ WRONG: if (balance == 0)
  Only finds subarrays starting from index 0

✓ RIGHT: if (map.containsKey(balance))
  Finds ALL balanced subarrays (anywhere)

HashMap with {0: -1} handles BOTH cases:
  1. balance = 0 (prefix from start)
  2. balance = any repeated value (subarray anywhere)


Algorithm Pattern:
═══════════════════════════════════════════════════════════════

Track running balance:
1. Initialize map with {0: -1}
2. For each element:
   a. Update balance (+1 for 1, -1 for 0)
   b. If balance exists in map:
      - Calculate length: current - first
      - Update max length
   c. If new balance: store it

Why Map Balance → Index?
═══════════════════════════════════════════════════════════════

We want to find when balance repeats:
- Store first occurrence
- When seen again, calculate distance
- Distance = length of balanced subarray

Space: O(n) because:
- At most n+1 different balances
- Range: from -n to +n

Why Index -1 for Balance 0?
═══════════════════════════════════════════════════════════════

Handles prefix balanced from start:

nums = [0, 1]

i=0: balance=-1
i=1: balance=0 (back to initial!)
     Found at -1
     length = 1 - (-1) = 2 ✓

Without {0: -1}, we'd miss this!

Time Complexity:
═══════════════════════════════════════════════════════════════

Single pass: O(n)
HashMap operations: O(1) average

Total: O(n)

Space Complexity:
═══════════════════════════════════════════════════════════════

HashMap stores balances: O(n)
Range of possible balances: -n to +n (2n+1 values)
But we only store what we see: at most n+1

🎯 Pattern Recognition

Problem Type: Find Maximum Length with Constraint
Core Pattern: Running Balance + HashMap

When to Apply:
✓ Binary array (0s and 1s)
✓ Equal count constraint
✓ Maximum length needed
✓ Contiguous/continuous subarray

Recognition Keywords:
- "Equal number of"
- "Binary array"
- "Maximum length"
- "Contiguous"

Similar Problems:
- Continuous Subarray Sum (LC 523) - Problem #50
- Longest Well-Performing Interval (LC 1124)
- Maximum Size Subarray Sum Equals k (LC 325)

Key Difference from Problem #50:
┌────────────────────────────────────────────┐
│ #50: Sum divisible by k                   │
│      Track: sum % k                       │
│      Goal: Check existence                │
│                                            │
│ #51: Equal 0s and 1s                      │
│      Track: balance (0→-1, 1→+1)          │
│      Goal: Find max length                │
└────────────────────────────────────────────┘

Both use HashMap, but different transformations!

🧠 Interview Strategy

Step 1: "Find longest subarray with equal 0s and 1s"
Step 2: "Transform: treat 0 as -1, problem becomes sum=0"
Step 3: "Use running balance (cumulative sum)"
Step 4: "HashMap tracks first occurrence of each balance"
Step 5: "Same balance = subarray with sum 0"
Step 6: "Calculate length, track maximum"
Step 7: "O(n) time with single pass"

Key Points to Mention:
- Recognize transformation to sum problem
- Treat 0 as -1, 1 as +1
- Running balance concept
- HashMap stores balance → first index
- Initialize {0: -1} for edge cases
- Store only first occurrence (maximize length)
- Time: O(n), Space: O(n)
- Single pass solution

Why Transformation?
"Instead of tracking two separate counts (0s and 1s),
I transform the problem by treating 0 as -1. This way,
equal counts means sum equals 0, which is much simpler
to track with a running balance and HashMap."

Why HashMap?
"The hashmap lets me instantly check if I've seen this
balance before in O(1), storing the earliest index to
maximize the distance when the balance repeats."

This is similar to problem #50! 🏆

📝 Quick Revision Notes

🎯 Core Concept:

🚨 CRITICAL: Check for SAME balance (not just balance=0)! Transform 0→-1, find longest subarray with sum=0 by tracking repeating balance values with HashMap. Store first occurrence to maximize length.

Why Not Just Check Balance = 0?

nums = [1,1,1,0,0]
Balance: +1, +2, +3, +2, +1 (never 0!)

Only checking balance = 0: return 0 ✗ WRONG!
Checking repeating balance: return 4 ✓ CORRECT!

Key: balance[i] = balance[j] means sum(i+1 to j) = 0

⚡ Quick Implementation (Optimal):

import java.util.HashMap;

class Test {
  public int findMaxLength(int[] a) {
    int res = Integer.MIN_VALUE;
    int len = a.length;

    // Approach 1 - using prefixsum array alone. O(N2)
    // // Transform 0 to -1 and keep 1 same.
    // for (int i = 0; i < len; i++) {
    // if (a[i] == 0) {
    // a[i] = -1;
    // }
    // }
    // // Find prefix sum
    // int[] prefixSum = new int[len + 1];
    // for (int i = 1; i <= len; i++) {
    // prefixSum[i] = prefixSum[i - 1] + a[i - 1];
    // }
    // // Find gap between indices where prefixsum value becomes equal to one
    // another
    // for (int i = 0; i <= len; i++) {
    // for (int j = i + 1; j <= len; j++) {
    // // whenever prefixsum becomes equal, calculate width among indices
    // // to find the maximum length
    // if (prefixSum[i] == prefixSum[j]) {
    // res = Math.max(res, j - i);
    // }
    // }
    // }

    // Approach 2 - using prefixsum and hashmap
    // Transform 0 to -1 and keep 1 same.
    for (int i = 0; i < len; i++) {
      if (a[i] == 0) {
        a[i] = -1;
      }
    }
    // Find prefix sum
    int[] prefixSum = new int[len + 1];
    for (int i = 1; i <= len; i++) {
      prefixSum[i] = prefixSum[i - 1] + a[i - 1];
    }
    // Map to track last index (so that we get max len) of a prefixsum
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i <= len; i++) {
      if (!map.containsKey(prefixSum[i])) {
        map.put(prefixSum[i], i); // one-time. Keep it low index always to get max res
      } else {
        res = Math.max(res, i - map.get(prefixSum[i]));
      }
    }

    return res == Integer.MIN_VALUE ? 0 : res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.findMaxLength(new int[] { 0, 1, 1, 1, 1, 1, 0, 0, 0 }));
    System.out.println(t.findMaxLength(new int[] { 0, 1 }));
    System.out.println(t.findMaxLength(new int[] { 0, 1, 0 }));
  }
}

🔑 Key Insights:

🚨 CRITICAL MISTAKE TO AVOID: Don't just check balance = 0!
Pattern: Running balance + HashMap
Transformation: 0 → -1, 1 → +1
Goal: Find subarray with sum = 0
Balance: Cumulative sum at each position
Why same balance works: balance[j] = balance[i] means sum(i+1 to j) = 0
Check: map.containsKey(balance) not balance == 0
Example breaking "balance=0 only": [1,1,1,0,0] → balance never 0 but answer is 4
HashMap: Maps balance → first index seen
Initialize: {0: -1} handles balanced prefix
Store once: Only first occurrence (maximize distance)
Length calc: i - map.get(balance) (NOT +1)
Update: Track maximum across all matches
Time: O(n) - single pass
Space: O(n) - at most n+1 different balances

🎪 Memory Aid:

"0 becomes -1! Sum = 0 means EQUAL! HashMap finds REPEATING balance!"
Think: "Balance tracker, same balance = answer!"

💡 The Transformation:

Original: Equal 0s and 1s
  [0, 1, 0, 1] → 2 zeros, 2 ones ✓

Transform: Sum = 0
  [-1, +1, -1, +1] → sum = 0 ✓

Same problem, easier to solve!

🔥 Why This Works:

If balance is same at two positions:
  balance[j] = balance[i]

Then:
  sum(i+1 to j) = balance[j] - balance[i]
                = 0

Sum = 0 means:
  -1s + 1s = 0
  count(0s) = count(1s) ✓

⚠️ Critical Details:

1. Initialize: map.put(0, -1)
2. Transform: (nums[i] == 0) ? -1 : 1
3. Store only first: if (!map.containsKey(balance))
4. Length: i - map.get(balance) (no +1)
5. Track maximum: Math.max(maxLen, length)

🎯 Comparison with Problem #50:

Problem #50 (Continuous Subarray Sum):
  Track: sum % k (remainders)
  Find: If divisible subarray exists
  Return: boolean

Problem #51 (Contiguous Array):
  Track: balance (0→-1, 1→+1)
  Find: Maximum length with sum=0
  Return: max length

Both use HashMap, different goals!

Continuous Subarray Sum (LC 523) - Problem #50
Longest Well-Performing Interval (LC 1124)
Maximum Size Subarray Sum Equals k (LC 325)
Subarray Sum Equals K (LC 560)

Happy practicing! 🎯

51. Contiguous Array

Problem Statement

🎨 Visual Understanding

The Problem Visualized

Key Observation: Transform to Balance Problem

🚨 CRITICAL: Why Check for SAME Balance (Not Just Balance = 0)?

The Insight: Use Running Balance (Revised)

Why This Works

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Prefix Sum Array

Better Approach 💡

Implementation

✅ Approach 3: HashMap with Running Balance (Optimal)

The Ultimate Optimization 💡

Implementation

🔍 Step-by-Step Execution

Approach 2 (Prefix Sum Array): nums = [1, 1, 1, 0, 0]

Approach 3 (HashMap): nums = [0, 1, 0, 1, 1, 0]

Example 2: nums = [0, 1, 0]

Example 3 (CRITICAL): nums = [1, 1, 1, 0, 0]

🔍 Edge Cases

Common Mistakes

🎯 Key Takeaways

⚡ Algorithm Comparison

🔑 The Core Insight

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

Related Patterns