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

def sol(arr):  

    zeros = [idx for idx, val in enumerate(arr) if val == 0]  
    if len(arr) == 0 or len(zeros) == 0:  
        return None  
    if len(arr) - 1 > zeros[-1]:  
        zeros.append(len(arr))  
    if len(zeros) == 1:  
        return zeros[0]  
    if len(zeros) == 2:  
        return max(zeros)  
    max_idx = None  
    diff = 0  
    for i in range(len(zeros) - 2):  
        # Calculating the difference of i+2 and i, since i+1 should be filled with 1 to find the max index  
        if zeros[i+2] - zeros[i] > diff:  
            diff = zeros[i + 2] - zeros[i] - 1  
            max_idx = zeros[i+1]  
    return max_idx  
    

arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]  
print(sol(arr))  

Answer 2

Here is little different algorithm

public static int zeroIndexToGetMaxOnes(int[] binArray) {
    int prevPrevIndex = -1, prevIndex = -1,currentLenght= -1, maxLenght = -1, requiredIndex = -1;

    for (int currentIndex = 0; currentIndex < binArray.length; currentIndex++) {
        if (binArray[currentIndex] == 0) {
            if (prevPrevIndex != -1) {
                currentLenght = currentIndex - (prevPrevIndex + 1);
                if (currentLenght > maxLenght) {
                    maxLenght = currentLenght;
                    requiredIndex = prevIndex;
                }
            }
            prevPrevIndex = prevIndex;
            prevIndex = currentIndex;
        } else {// case when last element is not zero, and input contains more than 3 zeros
            if (prevIndex != -1 && prevPrevIndex != -1) {
                currentLenght = currentIndex - (prevPrevIndex + 1);
                if (currentLenght > maxLenght) {
                    maxLenght = currentLenght;
                    requiredIndex = prevIndex;
                }
            }
        }
    }

    if (maxLenght == -1) { // less than three zeros
        if (prevPrevIndex != -1) { // 2 zeros
            if (prevIndex > (binArray.length - prevPrevIndex - 1)) {
                requiredIndex = prevPrevIndex;
            } else {
                requiredIndex = prevIndex;
            }

        } else { // one zero
            requiredIndex = prevIndex;
        }
    }
    return requiredIndex;
}

Here is the unit tests

@Test
public void replace0ToGetMaxOnesTest() {
    int[] binArray = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
    int index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(9));

    binArray = new int[]{1,0,1,1,1,0};
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(1));

    binArray = new int[]{0,1,1,1,0,1};
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(4));

    binArray = new int[]{1,1,1,0,1,0};
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(3));

    binArray = new int[]{0,1,1,1,0};
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(4));

    binArray = new int[]{1,1,1,1,0};
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(4));

    binArray = new int[]{0,1,1,1,1};
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
    assertThat(index, is(0));
}

Answer 3

Space Complexity - O(1)

Time Complexity - O(n)

A = map(int, raw_input().strip().split(' '))
left = 0  #Numbers of 1 on left of current index.
right = 0  #Number of 1 on right of current index.
longest = 0 #Longest sequence so far
index = 0
final_index = 0 # index of zero to get the longest sequence 
i = 0
while i < A.__len__():
    if A[i] == 0:
        left = right
        index = i
        i += 1
        right = 0
        while i < A.__len__() and A[i] != 0:
            right += 1
            i += 1
        if left + right + 1 > longest:
            final_index = index
            longest = left + right + 1

    else:
        right += 1
        i += 1

print final_index, longest

Answer 4

This C code implementation is based on the algorithm provided by @gordon-linoff above.

int maxOnesIndex1(bool arr[], int n)
{

    int prevZeroPos = 0;
    int oldOneCnt = 0;
    int newOneCnt = 0;
    int longestChainOfOnes = 0;
    int longestChainPos = 0;
    int i;

    for(i=0; i<n; i++)
    {

        if(arr[i]!=0)
        {
            oldOneCnt++;
        }
        else    // arr[i] == 0
        {
            prevZeroPos = i;
            newOneCnt = 0;

            // move by one to find next sequence of 1's
            i++;

            while(i<n && arr[i] == 1)
            {
                i++;
                newOneCnt++;
            }

            if((oldOneCnt+newOneCnt) > longestChainOfOnes)
            {
                longestChainOfOnes = oldOneCnt+newOneCnt+1;
                longestChainPos = prevZeroPos;
            }

            oldOneCnt = 0;
            i = prevZeroPos;

        }

    }

    if((oldOneCnt+newOneCnt) > longestChainOfOnes)
    {
        longestChainOfOnes = oldOneCnt+newOneCnt+1;
        longestChainPos = prevZeroPos;
    }

    return longestChainPos;
}

Answer 5

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 });
    }

}

Answer 6

Playing around with console yielded me this, touch up and cover edge case then you are good to go

function getIndices(arr, val) {
    var indexes = [], i = -1;
    while ((i = arr.indexOf(val, i+1)) != -1){
        indexes.push(i);
    }
    return indexes;
}

var a = [1,1,1,1,1,0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0];

var z = getIndices(a, 0);
z.unshift(0);

var longestchain = 0;
var target = 0;
for(var i=0;i<z.length;i++) {
    if(i == 0) { //first element
        longestchain = z[i] + z[i+1];
        target = i;
    } else if (i == z.length-1) { //last element
        var lastDistance = Math.abs(z[i] - z[i-1]);     
        if(lastDistance > longestchain) {
            longestchain = lastDistance;
            target = i;
        }
    } else { 
        if(Math.abs(z[i] - z[i+1]) > 1) { //consecutive 0s
            //look before and ahead
            var distance = Math.abs(z[i-1] - z[i]) + Math.abs(z[i] - z[i+1]);
            if(distance > longestchain) {
                longestchain = distance;
                target = i;         
            }
        }
    } 
}
console.log("change this: " + z[target]);

I first search for zeroes in the array and stored the position in another array, so in my e.g. you will get something like this [0,5,6,8,9,13,20], then i just run a single loop to find the greatest distance from each element with their adjacent ones, and storing the distance in the "longestchain", everytime i find a longer chain, i take note of the index, in this case "13".

Answer 7

Using Dynamic programming you can solve this code. Time complexity is O(n) and space complexity is O(n).

public static int Flipindex(String mystring){

    String[] arr = mystring.split(",");
    String [] arrays= new String[arr.length];
    for(int i=0;i<arr.length;i++){
        arrays[i]="1";
    }
    int lastsum = 0;
    int[] sumarray =new int[arr.length];
    for(int i=0;i<arr.length;i++){
        if(!arr[i].equals(arrays[i])){
            ++lastsum;              
        }
        sumarray[i]=lastsum;
    }
    int [] consecsum = new int [sumarray[sumarray.length-1]+1];

    for(int i: sumarray){
        consecsum[i]+=1;
    }

    int maxconsecsum=0,startindex=0;

    for(int i=0;i<consecsum.length-1;i++){
        if((consecsum[i]+consecsum[i+1])>maxconsecsum){
            maxconsecsum=(consecsum[i]+consecsum[i+1]);
            startindex=i;
        }
    }
    int flipindex=0;
    for(int i=0;i<=startindex;i++){
        flipindex+=consecsum[i];
    }
    return flipindex;

}


public static void main(String[] args) {
    String s= "1,1,0,0,1,0,1,1,1,0,1,1,1";
    System.out.println(Flipindex(s));   
}

Answer 8

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 9

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.