Longest Balanced Zeros and Ones
Problem
A log records each request as 1 for success and 0 for failure. Find the longest contiguous stretch of the log with exactly as many successes as failures, and return its length, or 0 if there is none. The log holds between 1 and 100,000 entries, so checking every stretch is too slow.
Examples
Input: bits = [0, 1, 0]
Output: 2
Why: [0, 1] and [1, 0] are both balanced; all three entries are notInput: bits = [0, 0, 1, 0, 0, 0, 1, 1]
Output: 6
Why: the last six entries hold three of eachInput: bits = [1, 1, 1]
Output: 0
Why: edge case, no stretch is balancedHints
0 / 3
Count a success as +1 and a failure as -1. A stretch is balanced exactly when its total is 0.
Keep a running total. A stretch from just after index i to index j sums to 0 when the running total at j equals the running total at i.
Store the first index at which each running total appears, with total 0 at index -1. When a total repeats, the stretch since its first appearance is balanced; only the first appearance is kept, because it gives the longest stretch.
Solution
Rewriting failures as -1 turns "equal counts" into "sum is zero", and a stretch sums to zero exactly when the running balance is the same at both of its ends. So the task becomes finding two equal balances as far apart as possible. A dictionary remembers the first index at which each balance appeared, seeded with balance 0 at index -1 so that balanced prefixes count too, and each later sighting of that balance is a candidate stretch. Later sightings are never stored, since the earliest one always gives the longer stretch. Time and space are both O(n).
def longest_balanced(bits):
first = {0: -1} # balance 0 before the first entry
balance = best = 0
for i, bit in enumerate(bits):
balance += 1 if bit else -1
if balance in first:
best = max(best, i - first[balance])
else:
first[balance] = i # keep only the earliest index
return best
print(longest_balanced([0, 1, 0])) # -> 2
print(longest_balanced([0, 0, 1, 0, 0, 0, 1, 1])) # -> 6
print(longest_balanced([1, 1, 1])) # -> 0Stuck on the idea rather than the code? Subarray Sums With a Map covers it.