Max Consecutive Ones III — With Circular Array Follow-up

Problem Statement

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

Constraints

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

Example

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

Output: 6

Explanation: Flip the 0s at index 5 and 10 → [1,1,1,0,0,1,1,1,1,1,1]. Longest run of 1s = 6 (indices 5-10).

What the Interviewer Expects

1. Sliding window approach — expand right pointer, count zeros in window. When zeros exceed k, shrink from left.
2. Track zero count — instead of actually flipping, just count zeros in current window. Window is valid while zeroCount <= k.
3. Answer = max window size seen across all valid windows.
4. Time: O(n), Space: O(1)

Follow-up: Circular Array

What if the array wraps around? The last element is adjacent to the first.

Approaches:

1. Double the array: concatenate nums + nums, apply same sliding window, but cap window size at n.
2. Two-pass: calculate the best window that wraps around by considering suffix of 1s at end + prefix of 1s at start.
3. Key insight: wrapping answer = suffix ones (from right) + prefix ones (from left) after using remaining flips.

Follow-ups

1. What if instead of flipping at most k zeros, you can flip exactly k? Does the approach change?
2. What if the array contains values 0, 1, 2 and you can only flip 0s?
3. Can you solve the circular version without doubling the array?
4. What if k is very large (k ≥ number of zeros)? What's the answer immediately?