Longest Run of Ones With One Fix

Medium

The tape bits consists of zeros and ones. You may turn at most one zero into a one. Return the greatest length of a contiguous stretch of ones you can obtain. Follow-up: how would you solve it if the numbers arrive one at a time as a stream and you cannot store them all?

Example 1

bits=[1, 1, 0, 1, 0, 1, 1, 1] → 5

Fixing the second zero gives [1, 1, 0, 1, 1, 1, 1, 1], five ones in a row. Fixing the first one gives only four.

Example 2

bits=[0, 0, 0] → 1

One position can become a 1, so the length is 1.

Example 3

bits=[1, 1, 1] → 3

Constraints

1 ≤ len(bits) ≤ 10⁵
bits[i] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Sliding Window

Similar problems

Evenly Stepped Stretches Medium Longest Shared Run Medium Sawtooth Readings Medium Two Separate Windows Medium Two Separate Segments With a Given Sum Medium

Input

bits=[1, 1, 0, 1, 0, 1, 1, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.