Max Consecutive Ones III
Problem Description
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 <= 105
nums[i]is either0or1.- 0 <= k <= nums.length
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach involves checking every possible subarray to determine the maximum number of consecutive ones you can achieve by flipping at most k zeros. This requires iterating over each subarray and counting the zeros in it.
Steps:
- Iterate through each possible starting point for the subarray.
- From each starting point, extend the subarray and count the number of zeros encountered.
- If the number of zeros exceeds
k, break out of the loop. - Keep track of the maximum length of such a subarray.
Code:
- Time Complexity: O(n^2) - We examine each subarray starting from every index.
- Space Complexity: O(1) - We use constant space for counters and storage.
2. Sliding Window
Intuition:
The sliding window technique efficiently finds the longest subarray with at most k zeros. The idea is to use two pointers to form a window and adjust it to keep track of the valid subarray as:
- Extend the right pointer to find a valid subarray with at most
kzeros. - If zeros exceed
k, shift the left pointer to make the subarray valid again by reducing the zeros count.
Steps:
- Initialize two pointers
leftandrightat the start of the array. - Increment the
rightpointer to expand the window. - Whenever a zero is encountered, increment the zero count.
- If the number of zeros exceeds
k, increment theleftpointer until the zeros count within the window is not more thank. - Keep track of the maximum window size encountered.
Code:
- Time Complexity: O(n) - Each element is processed at most twice (once by
rightand once byleft). - Space Complexity: O(1) - We use constant space for pointers and counters.