Given a binary array arr[] of length N, the task is to find the maximum consecutive ones that can be formed by deleting at most K 0′s from the array arr[] from any position.
Examples:
Input: arr[] = [0, 1, 1, 0, 1, 0, 1, 1], K = 2
Output: 5
Explanation: Delete 0’s at positions 3 and 5. Therefore, the maximum number of consecutive ones is 5.Input: arr[] = [1, 1, 1, 0, 0, 1, 1, 1, 0, 1], K = 1
Output: 4
Approach: The problem can be solved based on the following idea:
Use a sliding window, to keep track of no. of zeroes and ones. At any instance, if the number of zeroes in the current window exceeds the given value K, we can compress our window till we get the count of zeroes ? K. Any window with the count of zeroes <=k is eligible for the answer so we take the maximum of all possible answers at each step. Essentially what we do is find a valid window ( ? K 0’s ) and delete those 0’s ( allowed operation) and get max consecutive ones.
Steps were taken to implement the above approach:
- Initialize variables start = 0, and end = 0 as the start and end of the sliding window.
- Initialize variables zeros = 0 and ones = 0 to keep track of the count of ones and zeroes in the window.
- Initialize variable answer = 0 to keep track of the maximum answer.
- Now start a loop
- while ( end < size of arr ):
- if arr[end] is zero, the increment count of zeros.
- else increment count of ones.
- check if zeros > K: start++
- ans = max(ans, count of ones in valid window)
- end++;
- while ( end < size of arr ):
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum length of// consecutive onesint find_Max_Consecutive_Ones(int arr[], int n, int k){ int start = 0, end = 0, zeros = 0, ones = 0; int ans = 0; while (end < n) { if (arr[end] == 1) ones++; else zeros++; // Compressing window in case // required while (zeros > k) { if (arr[start] == 1) ones--; else zeros--; start++; } // Taking maximum of all possible // answers ans = max(ans, ones); // Expanding window end++; } return ans;}// Driver codeint main(){ int arr[] = { 1, 0, 1, 1, 0, 1, 0 }; int K = 2; int N = sizeof(arr) / sizeof(int); // Function call cout << find_Max_Consecutive_Ones(arr, N, K); return 0;} |
Java
// Java Code for the above approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { int[] arr = { 1, 0, 1, 1, 0, 1, 0 }; int K = 2; int N = arr.length; // Function call System.out.println(find_Max_Consecutive_Ones(arr, N, K)); } // Function to find maximum length of // consecutive ones public static int find_Max_Consecutive_Ones(int[] arr, int n, int k) { int start = 0, end = 0, zeros = 0, ones = 0; int ans = 0; while (end < n) { if (arr[end] == 1) ones++; else zeros++; // Compressing window in case // required while (zeros > k) { if (arr[start] == 1) ones--; else zeros--; start++; } // Taking maximum of all possible // answers ans = Math.max(ans, ones); // Expanding window end++; } return ans; }} |
Python3
def find_Max_Consecutive_Ones(arr, n, k): start = 0 end = 0 zeros = 0 ones = 0 ans = 0 while end < n: if arr[end] == 1: ones += 1 else: zeros += 1 while zeros > k: if arr[start] == 1: ones -= 1 else: zeros -= 1 start += 1 ans = max(ans, ones) end += 1 return ans# Driver codearr = [1, 0, 1, 1, 0, 1, 0]K = 2N = len(arr)# Function callprint(find_Max_Consecutive_Ones(arr, N, K))#//This article is written by ishan0202 |
Javascript
function findMaxConsecutiveOnes(arr, n, k) { let start = 0 let end = 0 let zeros = 0 let ones = 0 let ans = 0 while (end < n) { if (arr[end] === 1) { ones += 1 } else { zeros += 1 } while (zeros > k) { if (arr[start] === 1) { ones -= 1 } else { zeros -= 1 } start += 1 } ans = Math.max(ans, ones) end += 1 } return ans}// Driver codelet arr = [1, 0, 1, 1, 0, 1, 0]let K = 2let N = arr.length// Function callconsole.log(findMaxConsecutiveOnes(arr, N, K))//This article is written by ishan0202 |
C#
using System;class Program{ static int findMaxConsecutiveOnes(int[] arr, int n, int k) { int start = 0, end = 0, zeros = 0, ones = 0, ans = 0; while (end < n) { if (arr[end] == 1) ones++; else zeros++; while (zeros > k) { if (arr[start] == 1) ones--; else zeros--; start++; } ans = Math.Max(ans, ones); end++; } return ans; } static void Main() { int[] arr = { 1, 0, 1, 1, 0, 1, 0 }; int K = 2; int N = arr.Length; Console.WriteLine(findMaxConsecutiveOnes(arr, N, K)); }}//This article is written by ishan0202 |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
