MDSB - Editorial

PROBLEM LINK:

Practice

Contest

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.

1 Like

Please upvote guys, I need to ask questions. Thanks.
You Need PC Support

1 Like