Max Consecutive Ones III

Medium

Extra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.

Question

You get a list made only of 0s and 1s, and a number k. You may flip up to k of the 0s in the list into 1s.

After making your flips, find the length of the longest run of consecutive 1s you can create anywhere in the list.

Input: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2

Output: 6

Flipping two of the 0s in the middle turns the list into [1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0], creating a run of six 1s.

Input: nums = [0, 0, 1, 1, 1, 0, 0], k = 0

Output: 3

With no flips allowed, the longest run of 1s already in the list is the three in the middle.

Input: nums = [1, 0, 1, 0, 1, 0, 1], k = 2

Output: 5

Flipping the first two 0s turns the list into [1, 1, 1, 1, 1, 0, 1], a run of five 1s.

What are some questions you'd ask an interviewer?

What is the longest run of 1s you can create in [1, 1, 0, 0, 1, 1, 1, 0, 1, 1] if k = 2?

Take a moment to understand the problem and think of your approach before you start coding.