Longest Subarray with Equal Halves
Given an array of N integers, find the length of the longest contiguous subarray such that the number of occurrences of the integer '0' is equal to the number of occurrences of the integer '1'. You can assume the array only contains 0s and 1s.
Input
The first line contains an integer N, the size of the array. The second line contains N space-separated integers, where each integer is either 0 or 1.
Output
Print a single integer representing the length of the longest subarray with an equal number of 0s and 1s. If no such subarray exists, print 0.
Constraints
1 <= N <= 200000. The array elements are either 0 or 1.
Example 1
6 0 1 0 1 0 0
4
The subarray [0, 1, 0, 1] (indices 0 to 3) has two 0s and two 1s, length 4. The subarray [0, 1, 0, 0] (indices 2 to 5) has three 0s and one 1, not equal. The subarray [1, 0, 1, 0] (indices 1 to 4) has two 0s and two 1s, length 4. The longest is 4.
Example 2
5 1 1 1 0 0
4
The subarray [1, 1, 0, 0] (indices 1 to 4) has two 0s and two 1s, length 4. The subarray [1, 0] (indices 2 to 3) has one 0 and one 1, length 2. The longest is 4.
Hints
Similar problems
- Longest Subarray With Sum XMedium
- Count Subarrays with Target SumEasy
- XOR Pairs with Zero SumMedium
- Longest Subarray with Sum at Most KMedium
- Distinct Elements in a Sliding WindowMedium
- Matrix Zero Sum SubgridsMedium
More topics: Hash Map and Hashing problems, Sliding Window problems, Prefix Sums problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
6 0 1 0 1 0 0
5 1 1 1 0 0