## Wednesday, July 27, 2016

### Find size of the largest '+' formed by all ones in a binary matrix - GeeksforGeeks

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;`
`}`
Read full article from Find size of the largest '+' formed by all ones in a binary matrix - GeeksforGeeks