Given a binary array, find the index of 0 to be replaced with 1 to get maximum length sequence of continuous ones.
Consider the array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 }.
The index to be replaced is 7 to get continuous sequence of length 6 containing all 1’s.
The idea is very simple. We update each non-zero elements of array with count of their adjacent consecutive 1’s. For example, array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 } is converted to { 0, 0, 1, 0, 3, 3, 3, 0, 2, 2 }. Now the problem reduces to finding the index of 0 whose sum of left and right element is maximum.
Below is C and Java implementation of the same. Note that this approach will modify the array and at-least requires two traversals of the array. We can use an auxiliary array to avoid modification of original array or restore the original array before returning.
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <stdio.h> // Utility function to find max of two numbers int max(int x, int y) { return (x > y) ? x : y; } // Find index of 0 to replaced with 1 to get maximum sequence of // continuous 1's int findIndexofZero(int arr[], int n) { // arr[i] now stores the length of consecutive 1's ending at arr[i] for (int i = 1; i < n; i++) { if (arr[i] == 1) { arr[i] += arr[i - 1]; } } int count = 0; // traverse the array from right to left for (int i = n - 1; i >= 0; i--) { // update count to number of adjacent 1's which includes the // current element count = max(arr[i], count); // update array with count of adjacent 1's for each non-zero elem if (arr[i]) { arr[i] = count; } else { // reset the count if current element is 0 count = 0; } } int max_count = 0; // stores maximum number of 1's (including zero) int max_index = -1; // stores index of 0 to be replaced // consider each index i of the array for (int i = 0; i < n; i++) { // if current element is 0 if (arr[i] == 0) { // update maximum count and index of 0 to be replaced if // required by taking left and right element count if (i == 0 && max_count < arr[i + 1] + 1) { max_count = arr[i + 1] + 1, max_index = i; } else if (i == n - 1 && max_count < arr[i - 1] + 1) { max_count = arr[i - 1] + 1, max_index = i; } else if (max_count < arr[i - 1] + arr[i + 1] + 1) { max_count = arr[i - 1] + arr[i + 1] + 1, max_index = i; } } } // restore the original array for (int i = 1; i < n; i++) { if (arr[i]) { arr[i] = 1; } } // return index of 0 to be replaced or -1 if array contains all 1's return max_index; } // main function 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; } |
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
class FindIndexofZero { // Find index of 0 to replaced with 1 to get maximum sequence // of continuous 1's public static int findIndexofZero(int[] A) { // A[i] now stores the length of consecutive 1's ending at A[i] for (int i = 1; i < A.length; i++) { if (A[i] == 1) { A[i] += A[i - 1]; } } int count = 0; // traverse the array from right to left for (int i = A.length - 1; i >= 0; i--) { // update count to number of adjacent 1's which includes the // current element count = Math.max(A[i], count); // update array with count of adjacent 1's for each // non-zero element if (A[i] != 0) { A[i] = count; } else { // reset the count if current element is 0 count = 0; } } int max_count = 0; // stores maximum number of 1's (including 0) int max_index = -1; // stores index of 0 to be replaced // consider each index i of the array for (int i = 0; i < A.length; i++) { // if current element is 0 if (A[i] == 0) { // update maximum count and index of 0 to be replaced if // required by taking left and right element count if (i == 0 && max_count < A[i + 1] + 1) { max_count = A[i + 1] + 1; max_index = i; } else if (i == A.length - 1 && max_count < A[i - 1] + 1) { max_count = A[i - 1] + 1; max_index = i; } else if (max_count < A[i - 1] + A[i + 1] + 1) { max_count = A[i - 1] + A[i + 1] + 1; max_index = i; } } } // restore the original array for (int i = 1; i < A.length; i++) { if (A[i] != 0) { A[i] = 1; } } // return index of 0 to be replaced or -1 if array contains all 1's return max_index; } // main function 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
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
We have discussed two more approaches to solve this problem (here and here).
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply