Max Consecutive Ones III

Grow right, shrink left only when the flip budget goes negative

time O(n)space O(1)

Flipping is a red herring: a stretch is usable exactly when it contains at most k zeros, so nothing has to be changed in the array at all. Carry the flip budget as a counter. Every step the right edge takes in one more cell, paying a flip if that cell is a 0. The moment the budget goes negative the window is illegal, so the left edge walks right — refunding a flip each time it steps over a 0 — until it is legal again. The left edge never moves backwards, so each cell is entered once and left at most once and the whole scan is linear.

Details

Animated on: nums = [1,1,0,0,1,1,0,1,1], k = 2 — the longest run of 1s obtainable by flipping at most k zeros.

Problem:Max Consecutive Ones IIIMedium

Grow right, shrink left only when the flip budget goes negative

step 1 / 11

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

The run of 1s may be broken by 0s, but 2 of those 0s can be flipped. So the question is really: how wide can a stretch get while holding at most 2 zeros? One window that grows on the right and only gives ground on the left answers that in a single pass.

Pseudocode

1FUNCTION longestOnes(nums, k):
2  l <- 0
3  best <- 0
4  FOR r <- 0 TO LENGTH(nums) - 1:
5    IF nums[r] = 0:
6      k <- k - 1
7    WHILE k < 0:
8      IF nums[l] = 0:
9        k <- k + 1
10      l <- l + 1
11    best <- MAX(best, r - l + 1)
12  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 11 steps

The run of 1s may be broken by 0s, but 2 of those 0s can be flipped. So the question is really: how wide can a stretch get while holding at most 2 zeros? One window that grows on the right and only gives ground on the left answers that in a single pass.
nums[0] is already a 1, so it joins the window for free with 2 flips still unspent. "1" is 1 wide — a new best.
nums[1] is already a 1, so it joins the window for free with 2 flips still unspent. "11" is 2 wide — a new best.
nums[2] is a 0, so flipping it leaves 1 flip to spend. "110" is 3 wide — a new best.
nums[3] is a 0, so flipping it leaves 0 flips to spend. "1100" is 4 wide — a new best.
nums[4] is already a 1, so it joins the window for free with 0 flips still unspent. "11001" is 5 wide — a new best.
nums[5] is already a 1, so it joins the window for free with 0 flips still unspent. "110011" is 6 wide — a new best.
nums[6] is a 0 and the 2-flip budget is already spent, so the window cannot hold it as it stands. The left edge walks past 3 cells to index 3, which refunds the flip spent on the 0 at index 2 and makes the window legal again. "0110" is only 4 wide against the best of 6, so the record stands.
nums[7] is already a 1, so it joins the window for free with 0 flips still unspent. "01101" is only 5 wide against the best of 6, so the record stands.
nums[8] is already a 1, so it joins the window for free with 0 flips still unspent. "011011" ties the best of 6 without beating it, so the record stands.
Every right edge has been tried and the widest valid stretch was "110011" at indices 0..5: 6 cells holding just 2 zeros to flip. Return 6.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Max Consecutive Ones III in the editor All Sliding Window problems Back to roadmap