Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach 1
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity
3.
Approach 2
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity
4.
Frequently Asked Questions
4.1.
How do you find the starting and ending position (or) index of the longest continuous sequence of 1's in a binary array?
4.2.
What is the definition of a Binary Array?
4.3.
What is the algorithm for sliding windows?
4.4.
In Python, what is the sliding window algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find Index of 0 to be replaced with 1 to get the Longest Continuous Sequence of 1s in a Binary Array

Author Palak Mishra
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

When it comes to preparing for Coding Interviews, one of the most crucial data structures to understand is the array. In this article, we'll go over one of the most significant array operations.
Assume we have a single binary array. To acquire the most number of continuous sequences of 1s, we need to determine the position of 0 that can be substituted with 1.

Problem Statement

Find the index of 0 in a binary array that should be replaced with 1 to get the longest continuous sequence of ones.

Look at the array { 0, 0, 1, 0, 1, 1, 1, 1, 0, 1 } . To get a continuous sequence of length 6 containing all 1's, we need to replace index 8.

Sample Example

Array Input =

 [1,1,0,1,1,1]

 

Output:

 3

 

Explanation: Consecutive 1s appear in the first two or last three digits. Three 1s in a row is the maximum.

 

Array Input =

 [1,0,1,1,0,1]

 

Output: 

2

Approach 1

The idea is to count the number of ones on both sides of each zero. The required index is zero with the most ones surrounding it. During implementation, the following variables are used

  • leftCount
  • rightCount
  • maximumIndex
  • lastIndex
  • maxCount

Algorithm

  • Returns a 0 that should be replaced with 1 to obtain the longest continuous sequence of 1s. It returns -1 if there is no 0 in the array.
     
  • Count the number of ones on the left side of the current element zero.
     
  • Count the number of ones on the right side of the current element zero.
     
  • Keep the Index at zero with as many ones as possible surrounding it.
     
  • Keep track of the last zero elements you saw.
     
  • If the index maxInd is replaced by one, keep a count of ones.
     
  • Continue to increase the count until the current element is one.
     
  • Count the number of ones produced by replacing zero at index lastInd if the current zero element is not the first zero element. If necessary, adjust maxCnt and maxIndex.
     
  • When the last zero element is replaced by one, find the number of ones in a continuous series.

Implementation

// C++ program to find index of zero
// to be replaced by one to get longest
// continuous sequence of ones.
#include <bits/stdc++.h>
using namespace std;


int maxIndexofOnes(bool arr[], int n)
{
  int i = 0;
 
  int leftCount = 0;

  int rightCount = 0;
 
  int maximumIndex = -1;
 
  int lastIndex = -1;

  int maxCount = 0;

  while (i < n) {

          if (arr[i]) {
          rightCount++;
   }

        else {

             if (lastIndex != -1) {

             if (rightCount + leftCount + 1 > maxCount) {

                  maxCount = leftCount + rightCount + 1;

                  maximumIndex = lastIndex;
               }
            }

            lastIndex = i;

            leftCount = rightCount;

            rightCount = 0;
        }

     i++;
   }

   if (lastIndex != -1) {
         if (leftCount + rightCount + 1 > maxCount) {
                 maxCount = leftCount + rightCount + 1;
                 maximumIndex = lastIndex;
         }
   }
   return maximumIndex;
}

// Driver function
int main()
{
   bool arr[] = { 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1 };
   // bool arr[] = {1, 1, 1, 1, 0};

   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Index of 0 which is to be replaced is "
   << maxIndexofOnes(arr, n);
   return 0;
}

 

Output

Index of 0 which is to be replaced is 8

 

Complexity

  • Time Complexity: O(n) 
    The time it takes to traverse a linear array grows linearly in proportion to the number of elements in the array.
  • Auxiliary Space: O(1)
    Because we sort the input array in place, the space complexity of the methods described here is constant.

Also see,  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2

This is another efficient algorithm using which the problem can be solved in O(n) time. We will use three indexes in this approach.

Algorithm

  • The goal is to maintain track of three indexes: one, two, and three. Three indices must be kept track of. The current index (curr), the prior zero index (prevzero), and the previous to previous zero index (prevtoprevzero) are all examples of indexes (prevtoprevzero).
     
  • When the array element is 0, traverse the array and calculate the difference between curr and prevtoprevzero.
     
  • If the difference is more than max, the maximum is updated, and the index of the prev zero is returned with the maximum difference.

   Here's how to put the above algorithm into practice.

Implementation

#include<iostream>
using namespace std;
int findIndex(bool arr[], int n) {
   int count_of_maximum = 0;
   int index;
   int prevzero = -1;
   int prevtoprevzero = -1;
   for (int curr=0; curr<n; curr++) {
      if (arr[curr] == 0) {
         if (curr - prevtoprevzero > count_of_maximum){
            count_of_maximum = curr - prevtoprevzero;
            index = prevzero;
         }
         prevtoprevzero = prevzero;
         prevzero = curr;
      }
   }
   if (n-prevtoprevzero > count_of_maximum)
      index = prevzero;
   return index;
}
int main() {
   bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Index of 0 that is to be replaced is "<< findIndex(arr, n);
}

 

Output 

Index of 0 that is to be replaced is 8

 

Complexity

  • Time Complexity: O(n)
    The problem can be solved in O(n) time because we just visit the array for one time only.
  • Auxiliary Space: O(1)
    Constant complexity – no matter how big the input is, it takes the same amount of space.

Check out this problem - First And Last Occurrences Of X

Frequently Asked Questions

How do you find the starting and ending position (or) index of the longest continuous sequence of 1's in a binary array?

Iterate through it, keeping track of the most extended and current sequences of ones and updating the longest continuous sequence when a more extended sequence is discovered.

What is the definition of a Binary Array?

The binary array set is a compact data structure that allows you to add elements and test membership quickly. It essentially functions as a collection of sorted arrays of power-of-2 sizes.

What is the algorithm for sliding windows?

Programmers can simplify their code by using the Sliding Window algorithm. This algorithm does exactly what it says: it creates a window over a portion of data that can slide over it to capture different parts.

In Python, what is the sliding window algorithm?

The Window Sliding Technique is a computational technique that aims to replace nested loops with a single loop, thus reducing the time complexity.

Conclusion

The DSA problem discussed in this article is that there are N elements in our array, these elements either have a value of 0 or 1. To get the most extended contiguous sequence of 1s, find the position where 0 should be replaced with 1.

We use Sliding Window Algorithm to get the desired efficient result.

We hope that this article has helped you enhance your knowledge regarding the subject of Binary Array and longest continuous sequence.

After reading about the operations of arrays, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about array sorting algorithms, Square Root using binary search and  Find the minimum element in a sorted and Rotated Array  Also see time complexity and Complexity Analysis.

You can also practice some relevant problems at Coding Ninjas Studio such as:

  1. Next Greater and Smaller Element for Every Element in an Array
  2. Sort a Rotated Sorted Array
  3. Rotation Count
  4. Reversal algorithm for right rotation of an array
     

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Find all elements in an array which have at-least two greater elements.
Next article
Two Best Non-Overlapping Events
Live masterclass