The challenge
Return the longest contiguous run of ones obtainable by flipping at most k zeros in a binary array.
Every value is 0 or 1; k ≥ 0. The input is not modified.
Example
[1,1,1,0,0,0,1,1,1,1,0], k = 2 → 6.
Use the walkthrough below to inspect the input and each state change.
See Flip K zeros, step by step
Expand, shrink, and inspect the window state.
11 elements · zero-based indicesk = 2
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 29
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: [1,1,1,0,0,0,1,1,1,1,0] · k = 2
Current window is empty.
Put it into code
Treat each zero as one unit of cost. Maintain a window whose zero count fits the flip budget.
Indices are zero-based. C++ uses C++17 or later.
def longest_ones(nums, k):
left = zeros = best = 0
for right, value in enumerate(nums):
zeros += value == 0
while zeros > k:
zeros -= nums[left] == 0
left += 1
best = max(best, right - left + 1)
return best#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int longest_ones(const vector<int>& nums, int k) {
int left = 0, zeros = 0, best = 0;
for (int r = 0; r < (int)nums.size(); ++r) {
zeros += nums[r] == 0;
while (zeros > k) zeros -= nums[left++] == 0;
best = max(best, r - left + 1);
}
return best;
}