Maximum consecutive ones III. Find maximum consecutive ones in an array of 0s and 1s, If k flip is allowed.
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 we can flip k zeros.
For example:
Input – {1, 1, 0, 0, 0, 1, 1, 1, 1, 1}, k = 2 (We can flip two zeros)
Output: 7
Explanation:
In this example, If we can flip at most k (which is 2) zero. By flipping the zeros, here we can form following subarrays.
{1, 1, 1, 1} -> From index 0 to 3 (zero is present at index 2 and 3)
One subarray is from index 1 to 3 -> {1, 1, 1}
Another subarray is from index 2 to 3 (As both the element at this index is zero) -> {1, 1}
From index 3 to 9 -> {1, 1, 1, 1, 1, 1, 1}
Out of these, the maximum number of consecutive 1s in an array is 7 {1, 1, 1, 1, 1, 1, 1}.
This problem is the variation of maximum consecutive ones II.
In this tutorial, I am going to discuss a sliding window approach to solve this problem. Also, i have explained it’s java code.
Max consecutive ones iii video tutorial
Find longest substring without repeating characters
Maximum Consecutive Ones III (If K Flip is Allowed) – Java Code
This problem can be efficiently solved using sliding window approach. The idea here is to maintain a window containing at most k zeroes at any point (As k flip is allowed). For this we need two pointers start and end.
Initially start and end pointer points at 0th index. Then we move the end pointer till it satisfies the condition of at most k zero. When we found more than k zero in a window, we have to move start pointer until only k 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 |
//Maximum consecutive ones III public class MaxConsecutiveOnesIII { public static int countConsecutiveOnes(int[] arr, int k) { int maxConsecutiveOne = 0; int start = 0; int zeroCount = 0; for(int end = 0; end < arr.length; end++) { if(arr[end] == 0) { zeroCount++; } 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, 0, 1, 1, 1, 1, 1}; int k = 2; System.out.println(countConsecutiveOnes(arr, k)); } } |
Max consecutive ones iii video tutorial
Maximum Consecutive Ones III LeetCode Solution
Maximum consecutive ones LeetCode solution.
|
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 |
class Solution { public int longestOnes(int[] nums, int k) { int start = 0; int zeroFlip = 0; int maxConsecutives = 0; for(int end = 0; end < nums.length; end++) { if(nums[end] == 0) { zeroFlip++; } while(zeroFlip > k) { if(nums[start] == 0) { zeroFlip--; } start++; } maxConsecutives = Math.max(maxConsecutives, end-start+1); } return maxConsecutives; } } |
