Maximize ones with limited flips
Company: PayPal
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a binary array and an integer k, return the length of the longest contiguous subarray achievable by flipping at most k zeros to ones. Explain an efficient algorithm, its complexity, and how you would adapt it for a stream.
Quick Answer: This question evaluates proficiency with array algorithms, particularly sliding-window and two-pointer reasoning, complexity analysis, and the ability to adapt solutions for streaming data.
Given a binary array `nums` (containing only 0s and 1s) and an integer `k`, return the length of the longest contiguous subarray that can be made all 1s by flipping at most `k` of its zeros to ones.
This is the classic sliding-window / two-pointer problem: expand the right edge of a window, and whenever the window contains more than `k` zeros, shrink it from the left until the zero count is back within budget. The answer is the maximum window size seen.
**Efficient algorithm:** Maintain a window `[left, right]` and a running count of zeros inside it. As `right` advances, add the new element; if it makes the zero count exceed `k`, advance `left` (decrementing the zero count when the element leaving was a zero) until the window is valid again. Track the largest valid window length. This runs in O(n) time and O(1) extra space because each index is added and removed from the window at most once.
**Adapting for a stream:** The same window logic works online. You consume elements one at a time as they arrive (the `right` pointer), but you must keep the elements still inside the current window buffered (e.g. in a deque) so you can drop them from the left when the zero budget is exceeded. Memory is bounded by the current window size, which is at most O(answer) rather than O(n), so you never need the whole stream in memory at once — you only retain the active candidate window.
Constraints
- 1 <= nums.length <= 10^5 (the empty array is also handled and returns 0)
- nums[i] is 0 or 1
- 0 <= k <= nums.length
Examples
Input: ([1,1,1,0,0,0,1,1,1,1,0], 2)
Expected Output: 6
Explanation: Flip the two zeros at indices 4 and 5 (or use the run starting at index 5) to get the window [1,1,1,1,1,1] of length 6. A third zero cannot be afforded with k=2.
Input: ([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3)
Expected Output: 10
Explanation: With k=3 flips the longest reachable all-ones window has length 10.
Hints
- Think in terms of a window: what is the longest window that contains at most k zeros? Every zero in that window can be flipped to a one.
- Use two pointers. Expand the right pointer to grow the window; when the window holds more than k zeros, advance the left pointer until it is valid again.
- Each index enters and leaves the window at most once, so the whole scan is linear time with only a couple of counters as state.
- For a stream, the same logic works online if you buffer the elements currently inside the window (a deque) so you can drop them from the left when the zero budget is exceeded; memory stays bounded by the window size.