Algorithm/Insights
In the previous post we have seen how this can be done in O(n) time and without using extra space. Though that approach is optimized one, we think it's not that intuitive. In this article, we will discuss another more intuitive approach which runs in O(n) time but also requires O(n) extra space.
The basic idea to solve this problem is to find out number of 1's on the both side of each 0. The 0 which has the highest number of 1's around it is the 0 we are looking for. For example for array {0,0,1,1,1,1,0,0,1,1,1,1,0,1,1,0,1,0,1,1,1,1,0}
number of 1's around 0 with index 0 - 0
number of 1's around 0 with index 1 - 4
number of 1's around 0 with index 6 - 4
number of 1's around 0 with index 7 - 4
number of 1's around 0 with index 12 - 6
number of 1's around 0 with index 15 - 3
number of 1's around 0 with index 17 - 5
number of 1's around 0 with index 22 - 4
As you can see, if we replace 0 at index 12 with 1 we get sequence of 1's with length as 7 which would be the longest sequence we could get using this array.
In this algorithm, what we do is that we build a count array which would keep track of number of 1's on both side of each 0. For example, countArray[0] = 0 for above example and countArray[1] = 4. Now to build this array, we have to count number of 1's on both side of each 0. To do this, we traverse the input array two times. First time to count number of 1's on left side of each 0 and second time to count number of 1's on right side of each 0. First for loop runs from index 0 to last index and second for loops runs in the opposite direction. Both for loops basically count the number of 1's visited between last seen 0 and current 0 by keeping a running count of number of 1's. At each occurrence of 0, this running count is added in the corresponding countArray, then running count is reset to 0. At each occurrence of 1 this running count is incremented by 1. Both of these for loops run in O(n) time. Once we have the countArray, all we need do is to find out the index of the element with maximum value from this array.