Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.0 <= k <= nums.lengthThe key idea in #1004 Max Consecutive Ones III is to find the longest subarray containing only 1s after flipping at most k zeros. A highly efficient strategy is the sliding window technique. Expand a window across the array while counting how many zeros are inside it. If the number of zeros exceeds k, move the left pointer forward until the window becomes valid again.
This approach ensures that the window always represents the longest valid segment where at most k zeros can be flipped. By continuously updating the maximum window size, you can determine the answer in a single pass. Alternative thinking patterns may involve prefix sums or using binary search on the answer, but the sliding window solution is typically the most optimal and simplest to implement.
The sliding window approach runs in O(n) time since each element is processed at most twice, and it uses O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window | O(n) | O(1) |
| Prefix Sum + Binary Search | O(n log n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
One thing's for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there's no point in doing it, right? Think Sliding Window!
Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?
We don't have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don't actually have to flip the zeros here!).
The way to shrink or expand a window would be based on the number of zeros that can still be flipped and so on.
This approach involves using a sliding window distinguished by two pointers. The window expands by moving the right pointer and checks whether the number of zeros within the window exceeds the allowed count 'k'. If it does, we move the left pointer to shrink the window until the condition is satisfied. We aim to find the maximum window size that can be achieved following this condition.
Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice.
Space Complexity: O(1), as no additional space is used aside from variables.
1#include <stdio.h>
2
3int longestOnes(int* nums, int numsSize, int k) {
4 int left = 0, max_len = This C solution involves handling array index operations and uses standard integer manipulation to maintain the window for the longest segment of ones attained through permissible flipping of zeros.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of sliding window problems like Max Consecutive Ones III frequently appear in FAANG and other top tech interviews. They test a candidate's understanding of two-pointer techniques and efficient array traversal.
No complex data structure is required for this problem. Two pointers and simple counters are enough to implement the sliding window efficiently. This keeps the space complexity constant.
The optimal approach uses the sliding window technique. Maintain a window with at most k zeros and adjust the left pointer whenever the zero count exceeds k. This allows you to track the longest valid subarray in O(n) time.
Yes, the problem can also be approached using binary search on the length of the subarray combined with prefix sums. However, this method is typically slower than the sliding window solution and adds extra implementation complexity.