Max Consecutive Ones III

Medium

Longest window holding at most k zeros

Problem

Given a binary array and k, return the longest run of 1s if you may flip at most k zeros.

In simple words

Slide a window that may hold at most k zeros; shrink from the left when it holds too many.

The idea

Flipping is a red herring: the answer is the longest window containing at most k zeros. Count zeros as the window grows and shrink from the left whenever that count exceeds k.

The trick

Track only the zero count — the ones look after themselves.
The window length itself is the answer; no separate sum is needed.
O(n), one pass.

←→stepspaceplay

1/41

Brute force

timeO(n²)spaceO(1)

Every window.

1for (let i = 0; i < n; i++) {2  let zeros = 0;3  for (let j = i; j < n; j++) {4    if (nums[j] === 0) zeros++;5    if (zeros > k) break;6    best = Math.max(best, j - i + 1);7  }8}

Input

array: [1, 1, 0, 0, 1, 1, 1, 0, 1]

Memory

k: 2

Output

best: —
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output:: 6
Explanation:: Flipping 2 zeros yields a run of 6 ones.

Example 2

Input:: nums = [0, 0, 1, 1, 0], k = 1
Output:: 3
Explanation:: One flip stretches a window to length 3.

Example 3

Input:: nums = [1, 1, 1], k = 0
Output:: 3
Explanation:: No flips needed — already all ones.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.