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. Given the following code, what is the return value when the input string is "aabc"?

easy

A. 2

B. 1

C. -1

D. 0

Solution

1. Step 1: Trace frequency and first_index dictionaries

   For "aabc": freq={'a':2, 'b':1, 'c':1}, first_index={'a':0, 'b':2, 'c':3}

2. Step 2: Find minimum index with frequency 1

   Characters with count 1 are 'b' at index 2 and 'c' at index 3; minimum is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First unique char is 'b' at index 2 [OK]

Hint: Check frequency and first occurrence carefully [OK]

Common Mistakes:

• Returning character instead of index
• Off-by-one index errors
• Ignoring multiple unique chars

2. Consider the following Python code for grouping anagrams. What is the value of anagram_map after processing the input ["eat", "tea", "bat"]?

easy

A. [["eat", "tea"], ["bat"]]

B. [["eat"], ["tea"], ["bat"]]

C. [["eat", "bat"], ["tea"]]

D. [["bat", "tea"], ["eat"]]

Solution

1. Step 1: Trace first string "eat"

   Count array increments for 'e', 'a', 't'. Key tuple created and "eat" added to anagram_map[key].

2. Step 2: Trace second string "tea"

   Count array matches "eat"'s key, so "tea" appended to same list.

3. Step 3: Trace third string "bat"

   Count array differs, new key created, "bat" added to new list.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   "eat" and "tea" grouped, "bat" separate [OK]

Hint: Anagrams share identical frequency count keys [OK]

Common Mistakes:

• Confusing keys causing separate groups
• Appending to wrong list
• Off-by-one in count array

3. Given the following code snippet, what is the final output when calling isHappy(7)?

def sum_of_squares(num):
    return sum(int(d) ** 2 for d in str(num))

UNHAPPY_CYCLE = {4, 16, 37, 58, 89, 145, 42, 20}

def isHappy(n: int) -> bool:
    while n != 1 and n not in UNHAPPY_CYCLE:
        n = sum_of_squares(n)
    return n == 1

print(isHappy(7))

easy

A. false

B. true

C. The code runs infinitely

D. Raises a runtime error

Solution

1. Step 1: Trace sum_of_squares for n=7

   7 -> 7² = 49

2. Step 2: Iterate until n=1 or cycle detected

   49 -> 4²+9²=16+81=97 -> 9²+7²=81+49=130 -> 1²+3²+0²=1+9+0=10 -> 1²+0²=1 -> loop ends, returns true

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   7 is a happy number, code returns true [OK]

Hint: Trace sum_of_squares until 1 or cycle [OK]

Common Mistakes:

• Assuming 7 leads to cycle or infinite loop

4. What is the time complexity of the optimal prefix sum + hash map solution for checking if a continuous subarray sum is a multiple of k, given an input array of length n and integer k?

medium

A. O(n * k)

B. O(n^2)

C. O(n)

D. O(k)

Solution

1. Step 1: Analyze the main loop over n elements

   The algorithm iterates once over the array, performing O(1) operations per element.

2. Step 2: Consider hash map operations and modulo computations

   Hash map lookups and insertions are average O(1), modulo operations are O(1), so total is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming modulo k affects complexity multiplicatively
• Thinking hash map size depends on k linearly

5. The following code attempts to find the intersection of two arrays using the two-pointer approach. Which line contains a subtle bug that can cause incorrect results when duplicates exist?

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    intersection = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            intersection.append(nums1[i])
            i += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return intersection

medium

A. Line that sorts nums1

B. Line that sorts nums2

C. Line that increments j in the else clause

D. Line that increments i after appending intersection

Solution

1. Step 1: Identify the bug

   When nums1[i] == nums2[j], only i is incremented but j is not, causing infinite loop or missing duplicates.

2. Step 2: Correct fix

   Both i and j must be incremented to move past matched elements and handle duplicates correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incrementing only one pointer on match breaks correctness [OK]

Hint: Both pointers must advance on match [OK]

Common Mistakes:

• Incrementing only one pointer on match
• Modifying input arrays directly
• Forgetting to sort arrays