Max Consecutive Ones III

Medium

Problem

Given a binary array and k, return the length of the longest run of 1s you can get by flipping at most k 0s.

Example 1

Input:  nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

Test cases

Case 1

Input:    [1,1,1,0,0,0,1,1,1,1,0], 2
Expected: 6

Case 2

Input:    [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3
Expected: 10

Case 3

Input:    [0,0], 0
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Window with at most k zeros

Time O(n)Space O(1)

Expand right counting zeros; shrink left while more than k zeros are inside.

function longestOnes(nums, k) {
let l = 0, zeros = 0, best = 0;
for (let r = 0; r < nums.length; r++) {
if (nums[r] === 0) zeros++;
while (zeros > k) if (nums[l++] === 0) zeros--;
best = Math.max(best, r - l + 1);
}
return best;
}