Maximum consecutive ones II. Given an array which only consists of 0s and 1s. Write a code to find the maximum number of consecutive 1s in an array, if you can flip at most one 0.
For example:
Input: {1, 1, 0, 0, 1, 1, 1, 1, 1}
Output: 6
In this example, If we can flip at most one zero then the maximum number of consecutive 1s in an array is 6 {1, 1, 1, 1, 1, 1}.
How we can solve this problem? We can solve this problem using multiple approaches. In this tutorial, I am going to discuss a sliding window technique and it’s java code to solve this problem.
The explanation of this approach using a video tutorial is present at the end of this post.
Find maximum sum of a subarray of size k
Sort an array of 0s, 1s and 2s
Maximum Consecutive Ones II – Java Code
The idea here is to maintain a window containing at most one zeroes at any point. To solve this problem using a sliding window approach, what we can do is to maintain two pointers start and end.
Initially start and end pointer points to the 0th index. Then we move the end pointer till it satisfies the condition of at most one zero. When we found more than one zero in a window, we have to move start pointer until only one zero is left in this window.
The time complexity of this approach is O(n) and its space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
//Maximum Consecutive Ones II public class MaxConsecutiveOnesII { public static int countConsecutiveOnes(int[] arr) { int maxConsecutiveOne = 0; int start = 0; int k = 1; //Represent we can flip at most one 0 int zeroCount = 0; //Move end pointer/index for(int end = 0; end < arr.length; end++) { //If zero is found, then increment zeroCount if(arr[end] == 0) { zeroCount++; } /* If the value of zeroCount is greater than k, move start pointer and reset the window. */ while(zeroCount > k) { if(arr[start] == 0) { zeroCount--; } start++; } maxConsecutiveOne = Math.max(maxConsecutiveOne, end-start+1); } return maxConsecutiveOne; } public static void main(String[] args) { int[] arr = {1, 1, 0, 0, 1, 1, 1, 1, 1}; System.out.println(countConsecutiveOnes(arr)); } } |
