Find the index of 0 to be replaced to get the maximum length sequence of continuous ones
Given a binary array, find the index of 0 to be replaced with 1 to get the maximum length sequence of continuous ones.
For example, consider the array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 }. We need to replace index 7 to get the continuous sequence of length 6 containing all 1’s.
We can efficiently solve this problem in linear time and constant space. The idea is to traverse the given array and maintain an index of the previous zero encountered. We can then easily find out the total number of 1’s between the current zero and the last zero for each subsequent zeros. For each element, check if the maximum sequence of continuous 1’s ending at that element (including the last zero, which is now replaced by 1) exceeds the maximum sequence found so far. If yes, update the maximum sequence to the current sequence length and index of optimal zero and index the last zero encountered.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <stdio.h> // Find the index of 0 to replace with 1 to get the maximum sequence // of continuous 1's int findIndexofZero(int arr[], int n) { int max_count = 0; // stores maximum number of 1's (including zero) int max_index = -1; // stores index of 0 to be replaced int prev_zero_index = -1; // stores index of previous zero int count = 0; // stores current count of zeros // consider each index `i` in the array for (int i = 0; i < n; i++) { // if the current element is 1 if (arr[i] == 1) { count++; } // if the current element is 0 else { // reset count to 1 + number of ones to the left of current 0 count = i - prev_zero_index; // update `prev_zero_index` to the current index prev_zero_index = i; } // update maximum count and index of 0 to be replaced if required if (count > max_count) { max_count = count; max_index = prev_zero_index; } } // return index of 0 to be replaced or -1 if the array contains all 1's return max_index; } int main(void) { int arr[] = { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int index = findIndexofZero(arr, n); if (index != -1) { printf("Index to be replaced is %d", index); } else { printf("Invalid input"); } return 0; } |
Output:
Index to be replaced is 7
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Main { // Find the index of 0 to replace with 1 to get the maximum sequence // of continuous 1's public static int findIndexofZero(int[] A) { int max_count = 0; // stores maximum number of 1's (including 0) int max_index = -1; // stores index of 0 to be replaced int prev_zero_index = -1; // stores index of previous zero int count = 0; // stores current count of zeros // consider each index `i` in the array for (int i = 0; i < A.length; i++) { // if the current element is 1 if (A[i] == 1) { count++; } // if the current element is 0 else { // reset count to 1 + number of ones to the left of current 0 count = i - prev_zero_index; // update `prev_zero_index` to the current index prev_zero_index = i; } // update maximum count and index of 0 to be replaced if required if (count > max_count) { max_count = count; max_index = prev_zero_index; } } // return index of 0 to be replaced or -1 if the array contains all 1's return max_index; } public static void main (String[] args) { int[] A = { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 }; int index = findIndexofZero(A); if (index != -1) { System.out.print("Index to be replaced is " + index); } else { System.out.print("Invalid input"); } } } |
Output:
Index to be replaced is 7
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# Find the index of 0 to replace with 1 to get the maximum sequence # of continuous 1's def findIndexofZero(A): max_count = 0 # stores maximum number of 1's (including 0) max_index = -1 # stores index of 0 to be replaced prev_zero_index = -1 # stores index of previous zero count = 0 # stores current count of zeros # consider each index `i` in the list for i in range(len(A)): # if the current element is 1 if A[i] == 1: count = count + 1 else: # if the current element is 0 # reset count to 1 + number of ones to the left of current 0 count = i - prev_zero_index # update `prev_zero_index` to the current index prev_zero_index = i # update maximum count and index of 0 to be replaced if required if count > max_count: max_count = count max_index = prev_zero_index # return index of 0 to be replaced or -1 if the list contains all 1's return max_index if __name__ == '__main__': A = [0, 0, 1, 0, 1, 1, 1, 0, 1, 1] index = findIndexofZero(A) if index != -1: print("Index to be replaced is", index) else: print("Invalid input") |
Output:
Index to be replaced is 7
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the given sequence.
We have discussed two more approaches to solve this problem:
Find maximum length sequence of continuous ones (Using Sliding Window)
Find maximum length sequence of continuous ones (Using Sliding Window)
Find the maximum sequence of continuous 1’s formed by replacing at-most `k` zeros by ones
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)