Reasoning Into CodeArunank Divya Sharan · Python edition← Arunank’s portfolio
Module 05 · Sliding Windows

046. Longest Ones After K Flips

Bridge · Download this solution · All solutions and shared helpers

Problem

Given a binary list and nonnegative k, return the longest contiguous length that can be made all ones by changing at most k zeros to ones. The input is not actually modified. Empty input returns zero.

Examples

Example 1

longest_ones([1,1,1,0,0,0,1,1,1,1,0], 2)
=> 6

A six-element window needs exactly two flips.

Example 2

longest_ones([0, 0], 0)
=> 0

No zero can be included without a flip.

Example 3

longest_ones([], 3)
=> 0

There is no window.

Reveal the worked solution and reasoning

Why this mechanism works

The number of required flips is exactly the number of zeros in the window. Ones have no cost. This reduces the transformation story to an at-most-budget window: expand, repair excessive zero count, then commit the valid length.

State and boundaries

zeros is the count of zeros in [left,right+1). best is updated only after zeros<=k.

Protocol

  1. Count the incoming zero if present.
  2. While zeros exceeds k, remove the leftmost element's cost.
  3. Advance left during repair.
  4. Update best with the repaired length.

Visualization

window: 1 1 0 1 0 -> cost 2
add 0 -> cost 3
remove through the first 0 to restore budget 2

Python implementation

def longest_ones(nums, k):
    left = zeros = best = 0
    for right, value in enumerate(nums):
        zeros += int(value == 0)
        while zeros > k:
            zeros -= int(nums[left] == 0)
            left += 1
        best = max(best, right - left + 1)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

longest_ones([1,1,1,0,0,0,1,1,1,1,0], 2)

L2 longest_ones: left = zeros = best = 0
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=0

L3 longest_ones: for right, value in enumerate(nums):
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=0; right=0; value=1

L8 longest_ones: best = max(best, right - left + 1)
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=1; right=0; value=1

L3 longest_ones: for right, value in enumerate(nums):
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=1; right=1; value=1

L8 longest_ones: best = max(best, right - left + 1)
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=2; right=1; value=1

L3 longest_ones: for right, value in enumerate(nums):
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=2; right=2; value=1

L8 longest_ones: best = max(best, right - left + 1)
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=3; right=2; value=1

L3 longest_ones: for right, value in enumerate(nums):
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=0; zeros=0; best=3; right=3; value=0

... 17 intermediate state changes omitted ...

L3 longest_ones: for right, value in enumerate(nums):
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=4; zeros=2; best=6; right=10; value=0

L4 longest_ones: zeros += int(value == 0)
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=4; zeros=3; best=6; right=10; value=0

L6 longest_ones: zeros -= int(nums[left] == 0)
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=4; zeros=2; best=6; right=10; value=0

L7 longest_ones: left += 1
nums=[1, 1, 1, 0, 0, 0, 1, 1, ...]; k=2; left=5; zeros=2; best=6; right=10; value=0

Result: 6. A six-element window needs exactly two flips.

longest_ones([0, 0], 0)

L2 longest_ones: left = zeros = best = 0
nums=[0, 0]; k=0; left=0; zeros=0; best=0

L3 longest_ones: for right, value in enumerate(nums):
nums=[0, 0]; k=0; left=0; zeros=0; best=0; right=0; value=0

L4 longest_ones: zeros += int(value == 0)
nums=[0, 0]; k=0; left=0; zeros=1; best=0; right=0; value=0

L6 longest_ones: zeros -= int(nums[left] == 0)
nums=[0, 0]; k=0; left=0; zeros=0; best=0; right=0; value=0

L7 longest_ones: left += 1
nums=[0, 0]; k=0; left=1; zeros=0; best=0; right=0; value=0

L3 longest_ones: for right, value in enumerate(nums):
nums=[0, 0]; k=0; left=1; zeros=0; best=0; right=1; value=0

L4 longest_ones: zeros += int(value == 0)
nums=[0, 0]; k=0; left=1; zeros=1; best=0; right=1; value=0

L6 longest_ones: zeros -= int(nums[left] == 0)
nums=[0, 0]; k=0; left=1; zeros=0; best=0; right=1; value=0

L7 longest_ones: left += 1
nums=[0, 0]; k=0; left=2; zeros=0; best=0; right=1; value=0

Result: 0. No zero can be included without a flip.

Why the solution is correct

A window is feasible exactly when its zero count fits the flip budget. The repair loop discards the shortest prefix necessary to restore feasibility, leaving the longest feasible suffix ending at right. Every optimum has an endpoint considered by this scan.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Counting zero runs rather than individual zeros changes the budget. Mutating the input loses the original costs needed during repair.

Reasoning card

State: zeros is the count of zeros in [left,right+1). best is updated only after zeros<=k.

Invariant: Current window contains at most k zeros.

Decision to rehearse: Treat zeros as resource usage; repair when resource exceeds k.

Finish: Update best with the repaired length

Transfer exercise

Give each zero a different nonnegative conversion cost. Replace zero count by window cost and preserve the same repair logic.