Longest Run of Ones With k Fixes

Medium

The tape bits consists of zeros and ones, and you get a number fixes. You may turn at most fixes zeros into ones. Return the greatest length of a contiguous stretch of ones you can obtain.

Example 1

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

Fix the zeros at positions 3 and 4: positions 1 to 5 become [1, 1, 1, 1, 1], length 5. No choice of two zeros does better.

Example 2

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

Nothing may be fixed, so the longest run is a single 1.

Example 3

bits=[0, 0, 1, 0], fixes=4 → 4

There are enough fixes for every zero, so the whole tape becomes ones.

Constraints

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

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Prefix Sum Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Windows With a Small Product Medium Trim the Ends to a Target Medium Even Out With Increments Medium Rug Over Painted Stretches Medium

Input

bits=[0, 1, 1, 0, 0, 1, 0, 1], fixes=2

Expected

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