Maximum Length Subarray with Equal 0s and 1s

You are given an array of n binary integers (each either 0 or 1). Your goal is to find the maximum length of a contiguous subarray in which the number of 0s is equal to the number of 1s. In other words, you need to find the maximum length of a subarray such that \(\#0 = \#1\).

This problem can be efficiently solved using a prefix sum approach combined with a hash map to store the first occurrence of a cumulative sum. The idea is to treat 0 as -1, so that when the cumulative sum becomes 0, it indicates an equal number of 0s and 1s from the start to the current index. If the cumulative sum repeats, the subarray between the two occurrences has an equal number of 0s and 1s. The optimal solution runs in \(O(n)\) time complexity.

inputFormat

The first line of input contains an integer \(n\), the size of the binary array. The second line contains \(n\) space-separated integers (each either 0 or 1).

outputFormat

Output a single integer representing the maximum length of a contiguous subarray with equal number of 0s and 1s.

3
0 1 0

2