PROBLEM LINK:
Author: Md Shahid
Tester: Arkapravo Ghosh
Editorialist: Md Shahid
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
You have been given an binary array. You need to find maximum contiguous 1's length after replacing at most one 0.
QUICK EXPLANATION:
You need to count contiguous 1’s length by replacing at most one 0 every time and store it a variable and check it every time if it is greater than previous then update it with new value else keep it same and continue until the whole array is traversed.
EXPLANATION:
We can efficiently solve this problem in linear time and constant space. The idea is to traverse the given array and maintain index of previous zero encountered. Then for each subsequent zeroes, we can easily find out number of 1’s between current zero and last zero. For each element we check if maximum sequence of continuous 1’s ending at that element (including last zero which is now replaced by 1) exceeds maximum sequence found so far. If yes, we update the maximum sequence to current sequence length and index of optimal zero to index of last zero encountered.After traversing the whole array print or return the maximum length.
Algorithm
A is the array and N is its length. cnt is length contiguous 1’s at i th iteration after replacing at most one 0. maxcnt is maximum length of contiguous 1’s at i iteration after replacing at most one 0. preidx is the index of previous zero encountered.
solve(A,N)
- Initialize cnt = 0, maxcnt = 0, preidx = -1
- Run a roop fron i = 0 to i = N-1
- If A[i] == 1
- cnt = cnt +1
- Else cnt = i - preidx and preidx =i
- End If
- If cnt > maxcnt
- maxcnt= cnt
- End If
- Return maxcnt
Complexity :
This algorithm takes linear time to find the maximum length contiguous 1’s after replacing one zero. So the time complexity is O(N) and space complexity is O(1).
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.