PPractick

The problem

A factory's uptime log is a binary array (1 = machine running, 0 = down). Maintenance can retroactively "fix" up to k down periods. What's the longest stretch of consecutive 1s achievable after flipping at most k zeros? Rephrased: find the longest window containing at most k zeros. A sliding window handles it: extend the right end, count zeros, and whenever the count exceeds k, shrink from the left until it's back to k.

Example: [1,1,1,0,0,0,1,1,1,1,0], k = 2 → 6.

Function signature

int longestOnes(const vector<int>& nums, int k);

Test cases

Input (nums, k)	Output	Explanation
([1,1,1,0,0,0,1,1,1,1,0], 2)	6	Flip the last two 0s
([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3)	10
([0,0,0], 0)	0	No flips allowed
([1,1,1], 0)	3
([0,0,0,1], 4)	4	k may exceed the number of zeros

(Confirm: values are 0 or 1; flipping is optional; the answer is a length of contiguous elements.)

How interviewers phrase it

• "Given a binary array nums and an integer k, return the maximum number of consecutive 1s if you can flip at most k 0s" (LeetCode 1004).

Clarifying questions to ask

1. At most k flips, not exactly k? (At most.)
2. Can k be 0 or larger than the number of zeros? (Yes.)
3. Is the input size large? (Up to 10⁵, so O(n).)

Follow-ups to expect

1. "Why is it the longest window with at most k zeros?"
2. "Why can the left pointer only move forward?"
3. "Non-shrinking variant?"
4. "Streaming version with a huge array?"
5. "Complexity?"

Related questions

• Longest subarray with given sum K (positives) Medium
• Fruit Into Baskets Medium
• Maximum Points You Can Obtain from Cards Medium
• Subarrays with K Different Integers Medium
• Binary Subarrays With Sum Hard
• Count number of Nice subarrays Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in