Longest Balanced Subarray
HardPractice library · +30 XParrayshash mapsprefix sums
Given an array A of N integers, where each integer is either 0 or 1, find the length of the longest contiguous subarray that contains an equal number of 0s and 1s. If no such subarray exists, print 0.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N space-separated integers, each being either 0 or 1.
Output
Print a single integer representing the length of the longest balanced subarray.
Constraints
1 <= N <= 200000. Elements of A are 0 or 1.
Time limit 1 s (native code; slower languages get more)Memory 256 MB17 hidden tests
Example 1
Input
8 1 0 1 1 0 0 1 0
Output
8
The subarray from index 1 to 6 (0 1 1 0 0 1) has three 0s and three 1s, length 6. The subarray from index 0 to 7 (1 0 1 1 0 0 1 0) also has four 0s and four 1s, length 8. So the longest is 8.
Example 2
Input
5 1 1 1 1 1
Output
0
No 0s, so no balanced subarray possible. Length is 0.
Hints
# 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
8 1 0 1 1 0 0 1 0
Example 2 input
5 1 1 1 1 1