Skip to main content

1004. Max Consecutive Ones III

medium

Given a binary array and an integer k, return the longest contiguous subarray of 1s you can produce by flipping at most k zeros. Sliding-window with a bounded zero count.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Constraints

  • 1 <= nums.length <= 10^5
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Examples

Example 1

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

Explanation: Flip the two zeros at indices 5 and 10 to get [1,1,1,0,0,1,1,1,1,1,1]. The longest run of consecutive 1s is length 6 (indices 5..10 after flipping).

Example 2

Input
nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output
10

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Rephrase the question: find the longest window with at most k zeros inside it.

Hint 2

Grow the window by moving right; if the window holds more than k zeros, move left until it holds at most k again.

Hint 3

You never need to actually flip anything — you just need to know the largest valid window length.

Solution approach

Reveal approach

Maintain a sliding window [left, right] and a counter zeros tracking how many zeros currently sit inside. Expand right one step at a time: if nums[right] == 0, increment zeros. Whenever zeros exceeds k, advance left, decrementing zeros each time you slide past a zero, until the window is valid again. After each expansion, update the answer with the current window width (right - left + 1). The window never has to actually flip anything because the question is equivalent to finding the longest run that contains at most k zeros — once you know that length, you know the post-flip answer is identical.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • sliding-window
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Max Consecutive Ones III and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →