Get longest continuous sequence of 1s

Question

I recently encountered a problem statement it says:

Given an array of 0s and 1s, find the position of 0 to be 
replaced with 1 to get longest continuous sequence of 1s.

For example : Array- 1,1,0,0,1,0,1,1,1,0,1,1,1
Output - index 9

I tried a brute force approach replacing every encountered 0 with 1 and after each such replacement, i counted the largest continuous repetitive sequence of 1 and updated it every time.

Is there a better approach/algorithm to this problem?

Answer 1

There should be a one-pass solution to this. The overall idea is to count the ones and to add up the lengths for each zero as you go. Well, not each zero, just the last encountered one and the longest.

You need to keep track of two things:

• The longest chain so far.
• The previous zero value, along with the length of the preceding ones.

The process then goes as following:

1. Starting walking through the string until you encounter a zero. Keep track of the number of ones as you go.

2. When you hit the zero, remember the position of the zero along with the number of preceding 1s.

3. Count the 1s to the next zero.

4. Go back to the previous zero and add the new "ones" to the previous "ones". If this is longer than the longest chain, then replace the longest chain.

5. Remember this zero along with the preceding 1s.

6. Repeat until you have reached the end of the string.

7. At then end of the string, go back and add the length to the previous zero and replace the longest chain if appropriate.

Answer 2

You can imagine you have to maintain a set of 1 allowing only one 0 among them, so

1) walk over the array,
2) if you are getting a 1,
  check a flag if you are already in a set, if no, 
then you start one and keep track of the start,
  else if yes, you just update the end point of set
3) if you get a 0, then check if it can be included in the set, 
(i.e. if only one 0 surrounded by 1 "lonely zero" )
 if no, reset that flag which tells you you are in a set
 else 
    is this first time ? (store this 0 pos, initialized to -1)
      yes, then just update the zero position 
      else okk, then previous set, of one..zero..one gets finished here, 
now the new set's first half i.e. first consecutive ones are the previous set's last portion, 
so set the beginning of the set marker to last zero pos +1, update the zero position.

So when to get check if the current set is having highest length? See , we update the end point only in 2 -> else portion, so just check with max start, max end etc etc at that point and it should be enough

Answer 3

Here is my solution. It is clean, takes O(n) time and O(1) memory.

public class Q1 {
    public Q1() {       
    }

    public static void doit(int[] data) {       
        int state = 0;
        int left, right, max_seq, max_i, last_zero;             
        left = right = 0;
        max_seq = -1;
        max_i =  -1;

       // initialization
        right = data[0]; 
        last_zero = (data[0]==0) ? 0 : -1;
        for (int i = 1; i < data.length; i++) {
            state = data[i - 1] * 10 + data[i];
            switch (state) {
            case 00: //reset run
                left = right = 0;
                last_zero = i;
                break;

            case 01: // beginning of a run
                right++;                
                break;

            case 10:// ending of a run
                if(left+right+1>max_seq){
                    max_seq = left+right+1;
                    max_i = last_zero;
                }
                last_zero = i; //saving zero position
                left = right; // assigning left
                right = 0; // resetting right
                break;

            case 11: // always good
                right++;
                break;
            }
        }
        //wrapping up
        if(left+right+1>max_seq){
            max_seq = left+right+1;
            max_i = last_zero;
        }

        System.out.println("seq:" + max_seq + " index:" + max_i);
    }

    public static void main(String[] args) {            
        //Q1.doit(new int[] { 1,1,0,0,1,0,1,1,1,0,1,1,1 });
        Q1.doit(new int[] { 1,1,0,0,1,0,1,1,1,0,1,1,1 });
    }

}