Longest Subarray with Equal Number of Zeroes and Ones
HardPractice library · +30 XPtwo pointersprefix sumhash map
Given an array consisting of only 0s and 1s, find the length of the longest contiguous subarray with an equal number of 0s and 1s. If no such subarray exists, return 0.
Input
The first line contains an integer N, the size of the array. The second line contains N integers, each being either 0 or 1.
Output
Print a single integer, the length of the longest subarray with an equal number of 0s and 1s.
Constraints
1 <= N <= 200000. The array elements are only 0 or 1.
Time limit 1 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
7 0 1 0 0 1 1 0
Output
6
The longest subarray with equal 0s and 1s is [0, 1, 0, 0, 1, 1], with length 6.
Example 2
Input
5 0 0 0 0 0
Output
0
No subarray has an equal number of 0s and 1s, so the length is 0.
Hints
Similar problems
- Distinct Subarrays with Bounded SumHard
- Longest Subarray with Distinct ElementsHard
- Count Subarrays with Distinct ElementsMedium
- Array of SubarraysMedium
- Subarray XOR with TargetMedium
- Count Unique Element PairsMedium
More topics: Hash Map and Hashing problems, Two Pointers 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()
Example 1 input
7 0 1 0 0 1 1 0
Example 2 input
5 0 0 0 0 0