Contiguous Array (Equal 0s and 1s)

🎯

Contiguous Array (Equal 0s and 1s)

mediumHASH_MAPFacebookAmazon

Imagine analyzing a binary signal stream where you want to find the longest balanced segment with equal zeros and ones, crucial for error detection in communication.

💡 This problem asks for the longest contiguous subarray with equal numbers of 0s and 1s. Beginners often struggle because the problem requires transforming the input and using a hash map to track prefix sums, which is not immediately intuitive.

📋

Problem Statement

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

1 ≤ nums.length ≤ 10^5nums[i] is either 0 or 1

💡

Example

Input"[0,1]"

Output2

The entire array has equal number of 0s and 1s.

Input"[0,1,0]"

Output2

The longest contiguous subarray with equal 0s and 1s is [0,1] or [1,0].

• All zeros → 0 (no equal 1s)
• All ones → 0 (no equal 0s)
• Single element array → 0 (cannot have equal 0s and 1s)
• Alternating zeros and ones → length equals array length if even

⚠️

Common Mistakes

Not transforming 0 to -1 or equivalent

Cannot use prefix sum zero logic, leading to incorrect results

✅ Transform 0 to -1 or add +1/-1 during prefix sum calculation

Updating max length only when prefix sum changes, not when repeated

Misses longer subarrays, returns shorter length

✅ Update max length when prefix sum repeats, not only when new

Modifying input array when not allowed

May cause side effects or fail tests expecting input unchanged

✅ Use approach 3 to compute prefix sums without modifying input

Not initializing hash map with sum 0 at index -1

Misses subarrays starting at index 0

✅ Initialize map with {0: -1} before iteration

Using nested loops for large inputs

Leads to TLE and poor performance

✅ Use prefix sum + hash map approach for O(n) solution

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by checking every possible subarray, helping beginners understand the problem's requirements and why a naive solution is inefficient.

Intuition

Check every possible contiguous subarray and count zeros and ones to find the longest balanced subarray.

Algorithm

1. Initialize max_length to 0.
2. Use two nested loops to consider every subarray.
3. For each subarray, count zeros and ones.
4. Update max_length if zeros and ones are equal.

💡 The nested loops and counting inside make this approach easy to understand but inefficient for large inputs.

</>

Code

def findMaxLength(nums):
    max_length = 0
    n = len(nums)
    for start in range(n):
        count0 = 0
        count1 = 0
        for end in range(start, n):
            if nums[end] == 0:
                count0 += 1
            else:
                count1 += 1
            if count0 == count1:
                max_length = max(max_length, end - start + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(findMaxLength([0,1,0,1,1,1,0]))

Line Notes

max_length = 0Initialize to track the longest balanced subarray found so far

for start in range(n)Outer loop picks the start index of subarray

for end in range(start, n)Inner loop picks the end index of subarray

if count0 == count1Check if current subarray has equal zeros and ones

public class Solution {
    public static int findMaxLength(int[] nums) {
        int maxLength = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int count0 = 0, count1 = 0;
            for (int end = start; end < n; end++) {
                if (nums[end] == 0) count0++;
                else count1++;
                if (count0 == count1) {
                    maxLength = Math.max(maxLength, end - start + 1);
                }
            }
        }
        return maxLength;
    }

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

Line Notes

int maxLength = 0;Initialize max length to zero

for (int start = 0; start < n; start++)Outer loop selects start index

for (int end = start; end < n; end++)Inner loop selects end index

if (count0 == count1)Check if subarray is balanced

#include <iostream>
#include <vector>
using namespace std;

int findMaxLength(vector<int>& nums) {
    int maxLength = 0;
    int n = nums.size();
    for (int start = 0; start < n; start++) {
        int count0 = 0, count1 = 0;
        for (int end = start; end < n; end++) {
            if (nums[end] == 0) count0++;
            else count1++;
            if (count0 == count1) {
                maxLength = max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {0,1,0,1,1,1,0};
    cout << findMaxLength(nums) << endl;
    return 0;
}

Line Notes

int maxLength = 0;Initialize max length to zero

for (int start = 0; start < n; start++)Outer loop picks start index

for (int end = start; end < n; end++)Inner loop picks end index

if (count0 == count1)Check if current subarray is balanced

function findMaxLength(nums) {
    let maxLength = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let count0 = 0, count1 = 0;
        for (let end = start; end < n; end++) {
            if (nums[end] === 0) count0++;
            else count1++;
            if (count0 === count1) {
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

// Test
console.log(findMaxLength([0,1,0,1,1,1,0]));

Line Notes

let maxLength = 0;Initialize max length to zero

for (let start = 0; start < n; start++)Outer loop selects start index

for (let end = start; end < n; end++)Inner loop selects end index

if (count0 === count1)Check if subarray is balanced

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, counting zeros and ones inside inner loop is O(1).

💡 For n=1000, this means about 1,000,000 operations, which is slow but still feasible for small inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for large arrays but helps understand the problem and serves as a baseline.

🧠

Prefix Sum with Hash Map (Using Transformation)

💡 This approach transforms the problem by converting 0s to -1s and uses prefix sums with a hash map to find the longest subarray efficiently.

Intuition

Replace 0 with -1, then find the longest subarray with sum zero using prefix sums and a hash map to track first occurrences of prefix sums.

Algorithm

1. Transform the array: replace 0 with -1.
2. Initialize a hash map to store prefix sum indices with sum 0 at index -1.
3. Iterate through the array, compute prefix sums.
4. If prefix sum seen before, update max length with distance between indices.
5. Else, store prefix sum index.

💡 The key insight is that equal prefix sums mean the subarray between them sums to zero, indicating equal 0s and 1s.

</>

Code

def findMaxLength(nums):
    for i in range(len(nums)):
        if nums[i] == 0:
            nums[i] = -1
    prefix_sum = 0
    seen = {0: -1}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

# Driver code
if __name__ == '__main__':
    print(findMaxLength([0,1,0,1,1,1,0]))

Line Notes

if nums[i] == 0:Transform 0 to -1 to use sum zero logic

seen = {0: -1}Initialize prefix sum map with sum 0 at index -1 for subarrays starting at 0

prefix_sum += numUpdate running prefix sum

if prefix_sum in seen:Check if prefix sum seen before to find balanced subarray

import java.util.*;
public class Solution {
    public static int findMaxLength(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) nums[i] = -1;
        }
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, -1);
        int prefixSum = 0, maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            if (seen.containsKey(prefixSum)) {
                maxLength = Math.max(maxLength, i - seen.get(prefixSum));
            } else {
                seen.put(prefixSum, i);
            }
        }
        return maxLength;
    }

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

Line Notes

if (nums[i] == 0) nums[i] = -1;Transform 0 to -1 for sum zero logic

seen.put(0, -1);Prefix sum zero at index -1 to handle subarrays from start

prefixSum += nums[i];Update running prefix sum

if (seen.containsKey(prefixSum))Check if prefix sum seen before to find balanced subarray

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findMaxLength(vector<int>& nums) {
    for (int& num : nums) {
        if (num == 0) num = -1;
    }
    unordered_map<int, int> seen;
    seen[0] = -1;
    int prefixSum = 0, maxLength = 0;
    for (int i = 0; i < nums.size(); i++) {
        prefixSum += nums[i];
        if (seen.find(prefixSum) != seen.end()) {
            maxLength = max(maxLength, i - seen[prefixSum]);
        } else {
            seen[prefixSum] = i;
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {0,1,0,1,1,1,0};
    cout << findMaxLength(nums) << endl;
    return 0;
}

Line Notes

if (num == 0) num = -1;Transform 0 to -1 for sum zero logic

seen[0] = -1;Initialize prefix sum map with sum 0 at index -1

prefixSum += nums[i];Update running prefix sum

if (seen.find(prefixSum) != seen.end())Check if prefix sum seen before to find balanced subarray

function findMaxLength(nums) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) nums[i] = -1;
    }
    const seen = new Map();
    seen.set(0, -1);
    let prefixSum = 0, maxLength = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        if (seen.has(prefixSum)) {
            maxLength = Math.max(maxLength, i - seen.get(prefixSum));
        } else {
            seen.set(prefixSum, i);
        }
    }
    return maxLength;
}

// Test
console.log(findMaxLength([0,1,0,1,1,1,0]));

Line Notes

if (nums[i] === 0) nums[i] = -1;Transform 0 to -1 for sum zero logic

seen.set(0, -1);Initialize prefix sum map with sum 0 at index -1

prefixSum += nums[i];Update running prefix sum

if (seen.has(prefixSum))Check if prefix sum seen before to find balanced subarray

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through array with O(1) hash map operations per element.

💡 For n=100000, this means about 100000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This approach is optimal and commonly expected in interviews for this problem.

🧠

Prefix Sum with Hash Map (Without Modifying Input)

💡 This approach avoids modifying the input array by computing prefix sums on the fly, which is safer in some contexts and preferred in interviews.

Intuition

Instead of changing 0 to -1 in the array, treat 0 as -1 during prefix sum calculation, and use a hash map to track first occurrences of prefix sums.

Algorithm

1. Initialize prefix sum and hash map with sum 0 at index -1.
2. Iterate through the array, add +1 for 1 and -1 for 0 to prefix sum.
3. If prefix sum seen before, update max length with distance between indices.
4. Else, store prefix sum index.

💡 The key difference is computing prefix sums without changing the input array.

</>

Code

def findMaxLength(nums):
    prefix_sum = 0
    seen = {0: -1}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

# Driver code
if __name__ == '__main__':
    print(findMaxLength([0,1,0,1,1,1,0]))

Line Notes

prefix_sum = 0Initialize running prefix sum

prefix_sum += 1 if num == 1 else -1Add +1 for 1, -1 for 0 without modifying input

if prefix_sum in seen:Check if prefix sum seen before to find balanced subarray

seen[prefix_sum] = iStore first occurrence of prefix sum

import java.util.*;
public class Solution {
    public static int findMaxLength(int[] nums) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, -1);
        int prefixSum = 0, maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i] == 1 ? 1 : -1;
            if (seen.containsKey(prefixSum)) {
                maxLength = Math.max(maxLength, i - seen.get(prefixSum));
            } else {
                seen.put(prefixSum, i);
            }
        }
        return maxLength;
    }

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

Line Notes

seen.put(0, -1);Initialize prefix sum map with sum 0 at index -1

prefixSum += nums[i] == 1 ? 1 : -1;Add +1 for 1, -1 for 0 without modifying input

if (seen.containsKey(prefixSum))Check if prefix sum seen before to find balanced subarray

seen.put(prefixSum, i);Store first occurrence of prefix sum

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findMaxLength(const vector<int>& nums) {
    unordered_map<int, int> seen;
    seen[0] = -1;
    int prefixSum = 0, maxLength = 0;
    for (int i = 0; i < nums.size(); i++) {
        prefixSum += (nums[i] == 1) ? 1 : -1;
        if (seen.find(prefixSum) != seen.end()) {
            maxLength = max(maxLength, i - seen[prefixSum]);
        } else {
            seen[prefixSum] = i;
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {0,1,0,1,1,1,0};
    cout << findMaxLength(nums) << endl;
    return 0;
}

Line Notes

seen[0] = -1;Initialize prefix sum map with sum 0 at index -1

prefixSum += (nums[i] == 1) ? 1 : -1;Add +1 for 1, -1 for 0 without modifying input

if (seen.find(prefixSum) != seen.end())Check if prefix sum seen before to find balanced subarray

seen[prefixSum] = i;Store first occurrence of prefix sum

function findMaxLength(nums) {
    const seen = new Map();
    seen.set(0, -1);
    let prefixSum = 0, maxLength = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i] === 1 ? 1 : -1;
        if (seen.has(prefixSum)) {
            maxLength = Math.max(maxLength, i - seen.get(prefixSum));
        } else {
            seen.set(prefixSum, i);
        }
    }
    return maxLength;
}

// Test
console.log(findMaxLength([0,1,0,1,1,1,0]));

Line Notes

seen.set(0, -1);Initialize prefix sum map with sum 0 at index -1

prefixSum += nums[i] === 1 ? 1 : -1;Add +1 for 1, -1 for 0 without modifying input

if (seen.has(prefixSum))Check if prefix sum seen before to find balanced subarray

seen.set(prefixSum, i);Store first occurrence of prefix sum

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass with O(1) hash map operations per element, no input modification.

💡 This approach is as efficient as the previous but safer when input should not be changed.

Interview Verdict: Accepted

This is the preferred approach when input modification is disallowed or undesirable.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 or 3 is best for interviews; approach 1 is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code
2. Prefix Sum with Input Modification	O(n)	O(n)	No	Yes	Code this if input modification allowed
3. Prefix Sum without Input Modification	O(n)	O(n)	No	Yes	Preferred approach if input modification disallowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force approach to show understanding.Introduce the prefix sum transformation and hash map optimization.Discuss time and space complexity.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Ability to recognize prefix sum + hash map pattern, optimize brute force, and write clean code with edge case handling.

Common Follow-ups

• What if input cannot be modified? → Use approach 3.
• Can you find the actual subarray, not just length? → Track start index when updating max length.

💡 These follow-ups test deeper understanding and ability to adapt solutions to constraints.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest subarray with equal 0s and 1s; 2) Input is binary array; 3) Need contiguous subarray; 4) Constraints require efficient solution.

Signature Phrases

'equal number of 0 and 1''longest contiguous subarray''binary array'

NOT This Pattern When

Problems asking for non-contiguous subsequences or counting total number of subarrays, which require different approaches.

Similar Problems

Subarray Sum Equals K - similar prefix sum + hash map techniqueLongest Subarray with Equal Number of 0s and 1s II - variant with different constraints

Practice

1. Consider the following Python function that returns the maximum number of pairs summing to k. What is the returned value when calling maxOperations([1, 2, 3, 4], 5)?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace iterations for input [1, 2, 3, 4], k=5

   Iteration 1: num=1, complement=4, freq empty -> freq[1]=1
   Iteration 2: num=2, complement=3, freq={1:1} -> freq[2]=1
   Iteration 3: num=3, complement=2, freq[2]=1 > 0 -> count=1, freq[2]=0
   Iteration 4: num=4, complement=1, freq[1]=1 > 0 -> count=2, freq[1]=0

2. Step 2: Final count returned

   Count is 2 after processing all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pairs (1,4) and (2,3) sum to 5 [OK]

Hint: Pairs (1,4) and (2,3) found -> count 2 [OK]

Common Mistakes:

• Counting pairs multiple times
• Off-by-one in frequency decrement
• Confusing complement logic

2. Consider the following buggy code for counting subarrays with exactly k odd numbers. Which line contains the subtle bug that causes incorrect results for some inputs?

medium

A. Line with 'if nums[right] % 2 == 1: odd_count += 1'

B. Line with 'while odd_count >= k:'

C. Line with 'count += right - left + 1'

D. Line with 'return at_most_k(nums, k) - at_most_k(nums, k - 1)'

Solution

1. Step 1: Understand the window shrinking condition

   The window should shrink when odd_count > k, not when odd_count >= k, to correctly count subarrays with at most k odd numbers.

2. Step 2: Identify impact of bug

   Using '>=' shrinks the window too early, missing valid subarrays and causing undercount.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Changing '>=' to '>' fixes the counting [OK]

Hint: Window shrinks only when odd_count exceeds k, not equals [OK]

Common Mistakes:

• Using '>=' instead of '>' in while condition
• Miscounting subarrays due to early shrinking
• Confusing at_most_k with exactly k logic

3. Suppose the problem is modified so that the array can contain negative numbers, and you still need to find a continuous subarray of length at least 2 whose sum is a multiple of k. Which modification to the optimal approach is necessary to handle negative numbers correctly?

hard

A. Use a hash map to store all prefix sums instead of remainders modulo k

B. Adjust the modulo operation to handle negative remainders by adding k before modulo

C. No modification needed; the existing prefix sum remainder approach works unchanged

D. Switch to brute force since negative numbers break the remainder pattern

Solution

1. Step 1: Understand modulo behavior with negative numbers

   In many languages, modulo of negative numbers can be negative, causing incorrect remainder keys.

2. Step 2: Adjust modulo to always produce non-negative remainders

   By adding k before modulo (e.g., (running_sum % k + k) % k), remainders remain consistent and hash map keys valid.

3. Step 3: Confirm no other approach is needed

   Prefix sums and remainder hashing still work; only modulo adjustment is required.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling negative modulo correctly preserves remainder map logic [OK]

Hint: Normalize modulo to non-negative for negative numbers [OK]

Common Mistakes:

• Assuming no change needed
• Switching to brute force unnecessarily
• Storing full prefix sums instead of remainders

4. Suppose the problem changes: now you want the longest substring with at most two distinct characters, but characters can be reused infinitely many times and the input string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Maintain a sliding window with frequency counts but optimize by using a fixed-size array for frequencies instead of a hash map.

B. Use a brute force nested loop approach with early breaks to handle reuse.

C. Use a priority queue to track the least recently used character to evict when distinct count exceeds two.

D. Switch to a dynamic programming approach that stores results for substrings with reuse allowed.

Solution

1. Step 1: Understand reuse and input size impact

   Characters can be reused infinitely, but the problem remains longest substring with at most two distinct chars. The input is very long, so efficiency is critical.

2. Step 2: Identify efficient data structure

   Using a fixed-size array for frequencies (size 128 for ASCII) is more efficient than a hash map, reducing overhead and ensuring O(n) time and O(1) space.

3. Step 3: Confirm approach correctness

   The sliding window logic remains the same, but frequency tracking is optimized for speed and memory, suitable for very long inputs with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Fixed-size array frequency tracking is optimal for large inputs with limited charset [OK]

Hint: Fixed-size array beats hash map for fixed charset [OK]

Common Mistakes:

• Using brute force despite input size
• Using complex data structures unnecessarily
• Switching to DP without need

5. Suppose the input array can contain negative numbers and you want to find the number of subarrays whose sum equals k, but now you want to find the count of subarrays with sum divisible by k instead. Which modification to the optimal prefix sum with hash map approach correctly solves this variant?

hard

A. Use a sliding window approach since divisibility allows shrinking the window easily.

B. Track prefix sums modulo k and count frequencies of each remainder in a hash map.

C. Sort the array and use two pointers to find subarrays with sum divisible by k.

D. Use the original prefix sum approach without changes, as sum equals k and sum divisible by k are equivalent.

Solution

1. Step 1: Understand the problem variant

   We want subarrays where sum % k == 0, not sum == k.

2. Step 2: Modify prefix sums to track remainders

   Compute prefix sums modulo k and count how many prefix sums have the same remainder, since difference of prefix sums with same remainder is divisible by k.

3. Step 3: Use hash map to count frequencies of remainders

   Increment count by frequency of current remainder seen so far.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Sliding window fails with negatives; sorting breaks subarray continuity; original approach doesn't handle divisibility. [OK]

Hint: Use prefix sums modulo k and count remainder frequencies [OK]

Common Mistakes:

• Trying sliding window with negatives
• Ignoring modulo operation
• Assuming sum equals k and divisible by k are same