Maximum Consecutive Ones

Moderate
0/80
Average time to solve is 30m
96 upvotes
Asked in companies
DelhiveryFacebookMakeMyTrip

Problem statement

Given a binary array 'ARR' of size 'N', your task is to find the longest sequence of continuous 1’s that can be formed by replacing at-most 'K' zeroes by ones. Return the length of this longest sequence of continuous 1’s.

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (ARR).

The second line contains 'N' single space-separated binary values, representing the elements in the array.

The third line contains the value of 'K'.
Output format: 
For each test case, return the length of the longest subarray whose all elements are 1.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 5 * 10^4 
0 <= Arr[i] <= 1
0 <= K <= N

Time Limit: 1 sec
Sample Input 1:
1
7
1 0 0 1 1 0 1   
1
Sample Output 1:
4
Explanation of Sample Input 1:
Here we can replace at-most one 0 by 1 ( since K = 1 ). So the longest consecutive subarray with all 1’s that we can get is by replacing the 0 present at index 5.    

So the updated array will be {1,0,0,1,1,1,1}.

As we can see in the updated array the longest subarray with all 1’s is from index 3 of length 4.
Sample Input 2:
2
10
1 0 0 1 0 1 0 1 0 1
2
5
1 1 0 1 1
2
Sample Output 2:
5
5
Explanation of Sample Input 2:
Here, In the first test case we can replace at-most two 0’s by 1’s ( since 'K' = 2 ). So the longest consecutive subarray with all 1’s  we can get is by replacing the 0 present at index 4 and index 6 or index 6 and index 8 .    
So the updated array will be either {1,0,0,1,1,1,1,1,0,1} or {1,0,0,1,0,1,1,1,1,1}.

In the second test case there is only one zero in the whole array and we are allowed to replace two 0’s by 1’s so the answer will be the size of the array, i.e. 5.
Hint

Consider all possible subarrays.

Approaches (3)
Brute Force approach

The simplest way to find the required subarray would be to consider all the possible subarrays and compare the length at every point and store the longest length. If at any point, the current element is 0 and the value of ‘K’ is greater than 0, use it to convert the current element to 1. Else if the value of K is 0 , iterate further to find the next possible subarray.

 

Algorithm : 

  1. Loop over the array and if the current element of the array is ‘1’ find the length of the longest subarray starting with the current element.
  2. If the current element is ‘0’ , and the value of ‘K’ is greater than 0 , use it to convert the current element to ‘1’ and continue.
  3. While considering any particular subarray if the value of any element is 0 and the value of K is greater than 0, reduce K by 1 and consider the current element to be 1.
  4. At every step update the length of the longest subarray of 1’s found so far, print this value at the end.
Time Complexity

O(N^2), where ‘N’ is the number of elements in the array.

 

For each element of the array, the whole array is iterated. So, time complexity will be O(N^2).

Space Complexity

O(1)

 

Constant extra space is required.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Maximum Consecutive Ones
Full screen
Console