1004. Max Consecutive Ones III

At a Glance

Topic: sliding-window
Pattern: Sliding Window
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Microsoft
Frequency: High
LeetCode: 1004

Problem (one-liner)

Given a binary array nums and integer k, you may flip at most k zeros to ones. Return the length of the longest contiguous block of ones achievable.

Recognition Cues

Window may contain at most k zeros (after flips)
Maximize length with budget on zeros
Same algebra as character replacement: windowLen - onesInWindow ≤ k thinking

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — try every window, count zeros — O(n³) / O(n²).
Better — sliding window tracking zero count — O(n) time / O(1) space.
Optimal — expand; shrink while zeros in window > k.

Optimal Solution

Go

func longestOnes(nums []int, k int) int {
	left := 0
	zeros := 0
	best := 0
	for right := 0; right < len(nums); right++ {
		if nums[right] == 0 {
			zeros++
		}
		for zeros > k {
			if nums[left] == 0 {
				zeros--
			}
			left++
		}
		width := right - left + 1
		if width > best {
			best = width
		}
	}
	return best
}

JavaScript

function longestOnes(nums, maxZeros) {
	let left = 0;
	let zeros = 0;
	let best = 0;
	for (let right = 0; right < nums.length; right++) {
		if (nums[right] === 0) {
			zeros++;
		}
		while (zeros > maxZeros) {
			if (nums[left] === 0) {
				zeros--;
			}
			left++;
		}
		const width = right - left + 1;
		if (width > best) {
			best = width;
		}
	}
	return best;
}