Maximum consecutive ones formed by deleting at most K 0’s

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++;

Below is the implementation of the above approach:

Time Complexity: O(N) 
Auxilairy Space: O(1)

Related Articles:

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++;

Below is the implementation of the above approach:

Time Complexity: O(N) 
Auxilairy Space: O(1)

Related Articles: