O(n) time approach to find index of 0 to replace to get longest continuous sequence of 1s

Given a binary array, find the index of 0 such that when that 0 is replaced with 1 results in longest continuous sequence of 1's. For example, for array {0,1,1,1,0,1,0} replacing 0 at 0th index with 1 results in a sequence of 1's with length 4 and replacing 0 at index 4 with 1 results in a sequence of 1's with length 5. Hence for this input array, output returned should be 4.

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} longest sequence of 1's is obtained when we replace 0 at index 12 with 1.


Video coming soon!



Subscribe for more updates


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.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Finds the index of 0 such that when that 0 is replaced with 1 results in longest continuous sequence of 1's.
 * Runs in O(n) time.
 * @author Nilesh
 */

public class ReplaceZeroToGetOnes 
{
    private void buildCountArray(int[] array, int[] countArray)
    {
        // counts number of 1's between previous occurrence of 0 and current occurrence of 0
        int runningOneCount = 0;
        
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == 1)
            {
                runningOneCount += 1;
        
                // number of 1's around a 1 does not matter
                // to ignore them set it to -1 
                countArray[i] = -1;
            }
            else
            {
                countArray[i] = runningOneCount;
                runningOneCount = 0;
            }
        }
        
        runningOneCount = 0;
        for (int i = array.length-1; i > -1; i--)
        {
            if (array[i] == 1)
            {
                runningOneCount += 1;
                countArray[i] = -1;
            }
            else
            {
                countArray[i] += runningOneCount;
                runningOneCount = 0;
            }
        }
    }
    
    public int getRequiredIndex(int[] array)
    {
        int [] countArray = new int[array.length];
        
        buildCountArray(array, countArray);
        
        int maxCount = -1, reqIndex = 0;
        
        // find the index of 0 having maximum of number of 1's around it
        for (int i = 0; i < countArray.length; i++)
        {
            if (countArray[i] > maxCount)
            {
                reqIndex = i;
                maxCount = countArray[i];
            }
        }
        return reqIndex;
    }
    
    
    public static void main(String[] args)
    {
        ReplaceZeroToGetOnes solution = new ReplaceZeroToGetOnes(); 
        
        int [] binaryArray = {0,0,1,1,1,1,0,0,1,1,1,1,0,1,1,0,1,0,1,1,1,1,0};
        
        System.out.println(solution.getRequiredIndex(binaryArray));       
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More