#205MediumPrefix Sums & Difference Arrays· Prefix Balance with First-Seen Index

Longest Balanced Shift

A hospital logs each hour of a nurse's rota as `1` (on a ward shift) or `0` (on call at home). To keep workloads fair, the planner wants the longest run of consecutive hours in which the nurse spent **exactly as many hours on a ward as on call**. Given the array `shifts` of `0` and `1` values, return the length of the longest contiguous subarray that contains the same number of `0`s and `1`s. If no such subarray exists, return `0`.

Input format

`shifts`: an array of 0 and 1 values.

Output format

The length of the longest balanced contiguous subarray, or 0.

Examples

Input: shifts = [0, 1, 0]

Output: 2

The first two hours [0, 1] and the last two hours [1, 0] are balanced, so the longest has length 2.

Input: shifts = [0, 0, 1, 0, 0, 0, 1, 1]

Output: 6

The subarray from index 2 to 7 is [1, 0, 0, 0, 1, 1], which has three of each, so the answer is 6.

Input: shifts = [1, 1, 1]

Output: 0

There are no zeros, so no balanced stretch exists and the answer is 0.

Constraints

1 <= shifts.length <= 10^5
shifts[i] is 0 or 1

#prefix-sums
#hash-table
#binary-array
#longest-subarray