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.lengthThis 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.
This Python solution initializes two pointers 'left' and 'right' with 'left' starting from 0. As 'right' iterates over the array, it checks and counts zeros. If the count of zeros exceeds k, the 'left' pointer moves forward to reduce zeros count, effectively shrinking the window.
JavaScript
C++
Java
C#
C
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.
L4. Max Consecutive Ones III | 2 Pointers and Sliding Window Playlist • take U forward • 166,958 views views
Watch 9 more video solutions →Practice Max Consecutive Ones III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor