DSA problem
Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1s in the array if you can flip at most k zeros to ones. The flips are a budget you may distribute however you like, and the result must still be a contiguous run of ones after flipping.
At first glance this looks like it requires deciding which zeros to flip, but that decision is unnecessary. Within any contiguous window, flipping zeros to ones is always beneficial, so the only thing that limits us is how many zeros a window contains. A window is achievable as a run of all ones precisely when it holds at most k zeros.
This reframes the task neatly: find the longest contiguous window that contains no more than k zeros. The ones inside the window cost nothing, and the zeros consume the flip budget one unit each.
The intuition for the sliding window is to expand the right boundary and count the zeros currently inside the window. When the zero count exceeds k, the window is no longer achievable, so we advance the left boundary, decrementing the zero count whenever the left element was a zero. The maximum window width observed during this single pass is the answer, and both pointers move only forward for O(n) total work.
Examples
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 26nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 310nums = [0,0,0,0], k = 00Constraints
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1.
- 0 <= k <= nums.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.