Find size of the largest '+' formed by all ones in a binary matrix - GeeksforGeeks
Given a N X N binary matrix, find the size of the largest '+' formed by all 1s.
The idea is to maintain four auxiliary matrices left[][], right[][], top[][], bottom[][] to store consecutive 1’s in every direction.
Read full article from Find size of the largest '+' formed by all ones in a binary matrix - GeeksforGeeks
Given a N X N binary matrix, find the size of the largest '+' formed by all 1s.
The idea is to maintain four auxiliary matrices left[][], right[][], top[][], bottom[][] to store consecutive 1’s in every direction.
int findLargestPlus(int mat[N][N]){ // left[j][j], right[i][j], top[i][j] and // bottom[i][j] store maximum number of // consecutive 1's present to the left, // right, top and bottom of mat[i][j] including // cell(i, j) respectively int left[N][N], right[N][N], top[N][N], bottom[N][N]; // initialize above four matrix for (int i = 0; i < N; i++) { // initialize first row of top top[0][i] = mat[0][i]; // initialize last row of bottom bottom[N - 1][i] = mat[N - 1][i]; // initialize first column of left left[i][0] = mat[i][0]; // initialize last column of right right[i][N - 1] = mat[i][N - 1]; } // fill all cells of above four matrix for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { // calculate left matrix (filled left to right) if (mat[i][j] == 1) left[i][j] = left[i][j - 1] + 1; else left[i][j] = 0; // calculate top matrix if (mat[j][i] == 1) top[j][i] = top[j - 1][i] + 1; else top[j][i] = 0; // calculate new value of j to calculate // value of bottom(i, j) and right(i, j) j = N - 1 - j; // calculate bottom matrix if (mat[j][i] == 1) bottom[j][i] = bottom[j + 1][i] + 1; else bottom[j][i] = 0; // calculate right matrix if (mat[i][j] == 1) right[i][j] = right[i][j + 1] + 1; else right[i][j] = 0; // revert back to old j j = N - 1 - j; } } // n stores length of longest + found so far int n = 0; // compute longest + for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // find minimum of left(i, j), right(i, j), // top(i, j), bottom(i, j) int len = min(min(top[i][j], bottom[i][j]), min(left[i][j], right[i][j])); // largest + would be formed by a cell that // has maximum value if(len > n) n = len; } } // 4 directions of length n - 1 and 1 for middle cell if (n) return 4 * (n - 1) + 1; // matrix contains all 0's return 0;}