Longest Subarray With Equal 0s and 1s

MediumArraysHash mapPrefix sum303 tests

You are given an array bits that contains only 0 and 1.

A subarray is a part of the array made of neighbouring elements.

Find the longest subarray that has the same number of 0s and 1s. Return its length. If no such subarray exists, return 0.

Count each 1 as +1 and each 0 as -1. A subarray is balanced when its sum is 0, which means two prefix sums are equal. For each prefix sum, remember the first index where it appeared.

Examples

Example 1

Input:: [1,0,1,1,0,0,1]
Output:: 6

The first six elements 1, 0, 1, 1, 0, 0 have three 1s and three 0s. The whole array has 7 elements, an odd number, so it cannot be balanced.

Example 2

Input:: [1,1,1]
Output:: 0

There are no 0s, so no subarray is balanced.

Example 3

Input:: [0,0,1,0]
Output:: 2

The subarrays [0, 1] and [1, 0] are balanced and have length 2. Nothing longer is balanced.

Constraints

1 <= bits.length <= 30
bits[i] is 0 or 1.

Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.