Longest Balanced Binary Stretch
MediumArrays & Hashing
Problem
A quality-control line marks each item 1 if it passed and 0 if it failed. A shift lead wants the longest contiguous stretch of items with exactly as many passes as failures.
Given the binary array bits, return the length of the longest contiguous subarray containing an equal number of 0s and 1s, or 0 if there is none.
Example 1
- Input:
- bits = [0, 1, 1, 0, 1, 1, 1, 0]
- Output:
- 4
The first four items [0, 1, 1, 0] have two of each; no longer stretch is balanced.
Example 2
- Input:
- bits = [1, 1, 1]
- Output:
- 0
Example 3
- Input:
- bits = [0, 1]
- Output:
- 2
Constraints
- 1 ≤ bits.length ≤ 10^5
- bits[i] is 0 or 1.
Hint
Show the first hint
Rewrite the condition 'equal 0s and 1s' as a sum condition.
Walkthrough
How to approach it
01Clarify before coding
- Does an empty stretch count? No; return 0 if no non-empty balanced stretch exists.
- Do I return the stretch or its length? Only the length.
- Is the input strictly 0/1? Yes.
02Brute force
For each start, extend the end while counting zeros and ones, recording the longest point where they are equal.
Cost: O(n²) time: 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.