1004. Max Consecutive Ones III

How to solve Max Consecutive Ones III (LeetCode 1004): the approach in brief

The 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.

Pattern

Max Consecutive Ones III is a Sliding Window problem, in the Variable Size (Condition-Based) subpattern. The pattern covers fixed-size, variable-size, and character frequency matching window techniques

Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Approach outline

1. One thing's for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there's no point in doing it, right? Think Sliding Window!
2. Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?
3. We don't have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don't actually have to flip the zeros here!).

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Max Consecutive Ones III has been reported in interviews at Facebook, Coupang, HBO.