CODEWITHSUNDEEP
algorithmdata-structures
pyroCoder
pyroCoder

Reputation: 170

Finding longest sequence of '1's in a binary array by replacing any one '0' with '1'

I have an array which is constituted of only 0s and 1s. Task is to find index of a 0, replacing which with a 1 results in the longest possible sequence of ones for the given array. Solution has to work within O(n) time and O(1) space.

Eg:

Array - 011101101001
Answer - 4 ( that produces 011111101001)

My Approach gives me a result better than O(n2) but times out on long string inputs. 

int findIndex(int[] a){

    int maxlength = 0; int maxIndex= -1;
    int n=a.length;
    int i=0; 
    while(true){

        if( a[i] == 0 ){
            int leftLenght=0;
            int j=i-1;
            //finding count of 1s to left of this zero
            while(j>=0){
                if(a[j]!=1){
                    break;
                }
                leftLenght++;
                j--;
            }

            int rightLenght=0;
            j=i+1;
            // finding count of 1s to right of this zero
            while(j<n){
                if(a[j]!=1){
                    break;
                }
                rightLenght++;
                j++;
            }

            if(maxlength < leftLenght+rightLenght + 1){
                maxlength = leftLenght+rightLenght + 1;
                maxIndex = i;
            }
        }
        if(i == n-1){
            break;
        }
        i++;
    }
    return maxIndex;
}

Upvotes: 0

Views: 1491

Answers (3)

Nilesh
Nilesh

Reputation: 1343

I believe the problem can we solved by just maintaining a variable which stores the last trails of 1's that we saw before reaching a '0'.

int last_trail = 0;
int cur_trail = 0;
int last_seen = -1;
int ans = 0, maxVal = 0;
for(int i = 0; i < a.size(); i++) {
    if(a[i] == '0') {
        if(cur_trail + last_trail + 1 >  maxVal) {
            maxVal = cur_trail + last_trail + 1;
            ans = last_seen;
        }
        last_trail = cur_trail;
        cur_trail = 0;
        last_seen = i; 
    } else {
        cur_trail++;
    }
}
if(cur_trail + last_trail + 1 >  maxVal && last_seen > -1) {
    maxVal = cur_trail + last_trail + 1;
    ans = last_seen;
}

Upvotes: 1

proofbycontradiction
proofbycontradiction

Reputation: 3

This can be solved by a technique that is known as two pointers. Most two-pointers use O(1) space and O(n) time.

Code : https://www.ideone.com/N8bznU

#include <iostream>
#include <string>
using namespace std;


int findOptimal(string &s) {
    s += '0'; // add a sentinel 0
    int best_zero = -1;
    int prev_zero = -1;
    int zeros_in_interval = 0;
    int start = 0;
    int best_answer = -1;
    for(int i = 0; i < (int)s.length(); ++i) {
        if(s[i] == '1') continue;
        else if(s[i] == '0' and  zeros_in_interval == 0) {
            zeros_in_interval++;
            prev_zero = i;
        }
        else if(s[i] == '0' and zeros_in_interval == 1) {
            int curr_answer =  i - start; // [start, i) only contains one 0
            cout << "tried this : [" << s.substr(start, i - start) << "]\n";
            if(curr_answer > best_answer) {
                best_answer = curr_answer;
                best_zero = prev_zero;
            }
            start = prev_zero + 1;
            prev_zero = i;
        }
    }
    cout << "Answer = " << best_zero << endl;
    return best_zero;
}
int main() {
    string input = "011101101001";
    findOptimal(input);
    return 0;
}

This is an implementation in C++. The output looks like this: 

tried this : [0111]
tried this : [111011]
tried this : [1101]
tried this : [10]
tried this : [01]
Answer = 4

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

The approach is simple, you just need to maintain two numbers while iterating through the array, the current count of the continuous block of one, and the last continuous block of one, which separated by zero.

Note: this solution assumes that there will be at least one zero in the array, otherwise, it will return -1

int cal(int[]data){
    int last = 0;
    int cur = 0;
    int max = 0; 
    int start = -1; 
    int index = -1;
    for(int i = 0; i < data.length; i++){
        if(data[i] == 0){
           if(max < 1 + last + cur){
              max = 1 + last + cur;
              if(start != -1){
                index = start;
              }else{
                index = i;
              }
           }
           last = cur;
           start = i;
           cur = 0;  
        }else{
            cur++;
        }
    }
    if(cur != 0 && start != -1){
       if(max < 1 + last + cur){
          return start;
       }
    }     
    return index;
}

O(n) time, O(1) space

Live demo: https://ideone.com/1hjS25

Upvotes: 2

Related Questions