Subarray with Equal Number of 0s and 1s

📋

Problem

Imagine analyzing a binary signal to find the longest balanced segment where zeros and ones appear equally, crucial for error detection in communication systems.

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

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

Edge cases: All zeros → output 0 (no equal subarray)All ones → output 0 (no equal subarray)Single element array → output 0 (cannot have equal 0s and 1s)

</>

IDE

def findMaxLength(nums: list[int]) -> int:public int findMaxLength(int[] nums)int findMaxLength(vector<int>& nums)function findMaxLength(nums)

def findMaxLength(nums):
    # Write your solution here
    pass

class Solution {
    public int findMaxLength(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMaxLength(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findMaxLength(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning 0 due to missing prefix sum tracking or never updating max length.✅ Initialize hash map with sum 0 at index -1 and update max length when prefix sum repeats.

Wrong: length of first balanced subarray found instead of longestGreedy approach that stops at first balanced subarray.✅ Continue scanning entire array and update max length whenever prefix sum repeats at a later index.

Wrong: Incorrect length due to treating 0 and 1 as separate counts without prefix sum conversionNot converting 0 to -1, causing incorrect running sum calculations.✅ Convert 0 to -1 before computing prefix sums to track balance correctly.

Wrong: Crashes or errors on empty inputNo check for empty array before processing.✅ Add base case to return 0 if input array is empty.

Wrong: Timeout on large inputsUsing O(n^2) brute force approach.✅ Implement O(n) prefix sum with hash map approach to pass performance tests.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Think about common algorithmic traps like greedy and off-by-one errors.

Optimize your solution to linear time using prefix sums and hash maps.

t1_01basic

Input{"nums":[0,1]}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Try tracking the difference between counts of 0s and 1s as you iterate.

💡 Use a prefix sum approach with a hash map to store first occurrences of each difference.

💡 When the same difference repeats, the subarray between indices has equal 0s and 1s.

Why it failed: Returned incorrect length; likely missed updating max length when difference repeats. Fix by storing first occurrence of each prefix sum difference and updating max length accordingly.

✓ Correctly identifies longest balanced subarray using prefix sums and hash map.

t1_02basic

Input{"nums":[0,1,0,1,1,1,0]}

Expected4

⏱ Performance - must finish in 2000ms

Longest balanced subarray is [0,1,0,1] with length 4.

💡 Consider converting 0s to -1s to track running sum.

💡 Use a hash map to record earliest index of each running sum.

💡 Update max length when the same running sum is seen again.

Why it failed: Incorrect max length; likely failed to convert 0s to -1s or track earliest indices properly. Fix by mapping 0 to -1 and storing first occurrence of sums.

✓ Correctly computes max length by tracking running sums and earliest indices.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so result is 0.

💡 Check how your code handles empty input arrays.

💡 Ensure no index errors occur and return 0 if array is empty.

💡 Add a base case to return 0 when input length is zero.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty array and returning 0 immediately.

✓ Handles empty input gracefully, returning 0.

t2_02edge

Input{"nums":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single element cannot have equal number of 0s and 1s.

💡 Consider that subarrays must have length at least 2 to be balanced.

💡 Check that your code does not count single elements as balanced.

💡 Return 0 if no balanced subarray found.

Why it failed: Returned non-zero for single element input. Fix by ensuring subarray length is at least 2 when updating max length.

✓ Correctly returns 0 for single element arrays.

t2_03edge

Input{"nums":[0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All zeros means no subarray with equal 0s and 1s.

💡 Check if your code correctly handles arrays with no 1s.

💡 Ensure max length remains 0 if no balanced subarray found.

💡 Verify prefix sums never repeat for balanced subarrays in this case.

Why it failed: Returned non-zero for all zeros input. Fix by correctly tracking prefix sums and not updating max length when no balanced subarray exists.

✓ Correctly returns 0 when no balanced subarray exists.

t3_01corner

Input{"nums":[0,1,1,0,1,1,1,0,0]}

Expected6

⏱ Performance - must finish in 2000ms

Longest balanced subarray is [1,0,1,1,1,0,0] partial balanced segment is [1,0,1,1,1,0,0] but max balanced is [1,0,1,1] or [0,1,1,0] length 4.

💡 Beware of greedy approaches that pick first balanced subarray found.

💡 Use prefix sums and hash map to find longest, not just first balanced subarray.

💡 Track earliest occurrence of each prefix sum to maximize length.

Why it failed: Greedy approach returns shorter subarray length. Fix by storing earliest prefix sum indices and updating max length on repeated sums.

✓ Correctly finds longest balanced subarray, not just first.

t3_02corner

Input{"nums":[0,0,1,1,0,1,0,1,1,0]}

Expected10

⏱ Performance - must finish in 2000ms

Entire array is balanced with equal number of 0s and 1s.

💡 Check that your code handles entire array balanced case.

💡 Ensure prefix sum zero at start is handled correctly.

💡 Initialize hash map with sum 0 at index -1 to cover full array.

Why it failed: Misses full array balanced case due to missing initial prefix sum entry. Fix by initializing hash map with sum 0 at index -1.

✓ Correctly returns full array length when balanced.

t3_03corner

Input{"nums":[1,1,1,0,0,0,1,0]}

Expected8

⏱ Performance - must finish in 2000ms

Entire array is balanced with equal number of 0s and 1s.

💡 Avoid confusion between 0/1 counts and prefix sums.

💡 Convert 0 to -1 to track running sum correctly.

💡 Update max length when running sum repeats.

Why it failed: Incorrect output due to treating 0 and 1 as separate counts without prefix sum. Fix by converting 0 to -1 and using prefix sums.

✓ Correctly handles 0/1 conversion and prefix sums.

t4_01performance

Input{"nums":[0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with alternating 0 and 1; O(n) solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use prefix sums and hash map for O(n) time complexity.

💡 Track earliest prefix sum indices to find max length efficiently.

Why it failed: Solution times out due to O(n^2) brute force approach. Fix by implementing O(n) prefix sum with hash map solution.

✓ Efficient O(n) solution passes within time limit.

Practice

1. Given the following Python code implementing the optimal approach for longest consecutive sequence, what is the value of max_len returned when the input is [1, 9, 3, 10, 4, 20, 2]?

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in num_set:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

easy

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify sequence starts

   Numbers without predecessor: 1 (0 not in set), 9 (8 not in set), 20 (19 not in set).

2. Step 2: Trace sequences from starts

   From 1: sequence is 1,2,3,4 -> length 4; from 9: 9,10 -> length 2; from 20: 20 -> length 1. Max length is 4.

3. Step 3: Re-examine carefully

   Check if 1,2,3,4 is the longest. Actually, 1,2,3,4 is length 4, but 1,2,3,4,5 is not present. So max length is 4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Longest consecutive sequence length is 4 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number
• Off-by-one in length calculation
• Ignoring duplicates

2. Consider the following code snippet implementing the optimal prefix sum with hash map approach. What is the final returned value when the input is nums = [1, 2, 3] and k = 3?

def subarraySum(nums, k):
    count = 0
    running_sum = 0
    prefix_counts = {0: 1}
    for num in nums:
        running_sum += num
        if running_sum - k in prefix_counts:
            count += prefix_counts[running_sum - k]
        prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
    return count

print(subarraySum([1, 2, 3], 3))

easy

A. 3

B. 0

C. 1

D. 2

Solution

1. Step 1: Trace running_sum and prefix_counts

   Iteration 1: running_sum=1, prefix_counts={0:1,1:1}, count=0 Iteration 2: running_sum=3, running_sum-k=0 in prefix_counts, count=1, prefix_counts={0:1,1:1,3:1} Iteration 3: running_sum=6, running_sum-k=3 in prefix_counts, count=2, prefix_counts={0:1,1:1,3:1,6:1}

2. Step 2: Return count

   Count is 2, representing subarrays [1,2] and [3].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Count matches expected subarrays summing to 3. [OK]

Hint: Track running_sum and prefix_counts carefully [OK]

Common Mistakes:

• Off-by-one errors in counting
• Forgetting to initialize prefix_counts with {0:1}
• Miscounting subarrays ending at current index

3. The following code attempts to find the longest contiguous subarray with equal 0s and 1s. Which line contains a subtle bug that causes incorrect results on some inputs?

medium

A. Line 6: Initializing seen as empty dictionary instead of {0: -1}

B. Line 5: Initializing max_length to 0

C. Line 4: Initializing prefix_sum to 0

D. Line 8: Updating max_length with max of current and new length

Solution

1. Step 1: Understand the role of seen dictionary initialization

   Seen must map prefix_sum 0 to index -1 to handle subarrays starting at index 0.

2. Step 2: Identify that initializing seen as empty misses subarrays starting at index 0

   Without {0: -1}, the code misses valid subarrays from the start, causing off-by-one errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Other lines are correct; only seen initialization causes subtle bugs [OK]

Hint: Always initialize seen with {0: -1} for prefix sums [OK]

Common Mistakes:

• Not initializing seen with 0:-1
• Overwriting earliest prefix sum indices
• Not transforming 0 to -1

4. The following code attempts to find the pivot index but contains a subtle bug. Which line contains the bug?

def pivotIndex(nums):
    total = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total - left_sum:
            return i
        left_sum += num
    return -1

medium

A. Line 6: left_sum += num

B. Line 4: for i, num in enumerate(nums):

C. Line 2: total = sum(nums)

D. Line 5: if left_sum == total - left_sum:

Solution

1. Step 1: Understand the condition

   The condition should check if left_sum equals right sum, which is total - left_sum - current num.

2. Step 2: Identify the bug

   The code incorrectly checks if left_sum == total - left_sum, missing subtracting the current num, causing wrong pivot detection.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct condition is left_sum == total - left_sum - num [OK]

Hint: Check if right sum calculation includes current element [OK]

Common Mistakes:

• Forgetting to subtract current num from total
• Misplacing sum updates
• Returning null instead of -1

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