How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at PayPal.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at PayPal during technical interviews.

Maximize ones with limited flips | PayPal Coding Question

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.

Input: ([], 0)

Expected Output: 0

Explanation: Empty array: no subarray, so the answer is 0.

Input: ([0], 0)

Expected Output: 0

Explanation: A single zero with no flips allowed cannot become a one, so the longest all-ones subarray has length 0.

Input: ([0], 1)

Expected Output: 1

Explanation: One flip turns the single zero into a one, giving a window of length 1.

Input: ([1,1,1,1], 0)

Expected Output: 4

Explanation: All ones already; no flips needed, the whole array of length 4 qualifies.

Input: ([0,0,0,0], 2)

Expected Output: 2

Explanation: Only 2 of the 4 zeros can be flipped, so the largest all-ones window has length 2.

Input: ([1,0,1,0,1,0,1], 10)

Expected Output: 7

Explanation: k exceeds the number of zeros (3), so the entire array of length 7 can be made all ones.

Input: ([0,0,0], 0)

Expected Output: 0

Explanation: No flips allowed and no existing ones, so the answer is 0.

Input: ([1,0,0,1,1,0,1], 2)

Expected Output: 5

Explanation: There are 3 zeros total but only 2 may be flipped. The best valid window covers indices 0..4 ([1,0,0,1,1], two zeros) giving length 5; including a third zero is not allowed.

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.

Quick Overview

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.