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 Sam K., 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

More Arrays practice problems

See all Arrays problems →