Pattern visualizer
Max Consecutive Ones III
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. 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..
Grow right, shrink left only when the flip budget goes negative
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.
1FUNCTION longestOnes(nums, k):2 l <- 03 best <- 04 FOR r <- 0 TO LENGTH(nums) - 1:5 IF nums[r] = 0:6 k <- k - 17 WHILE k < 0:8 IF nums[l] = 0:9 k <- k + 110 l <- l + 111 best <- MAX(best, r - l + 1)12 RETURN best
← / → step · space play · Home restart