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:
2Approach 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
134+ registered 
