# Calculate size of the largest plus of 1’s in binary matrix

Given a square matrix of 0’s and 1’s, calculate the size of the largest plus formed by 1’s.

For example, for matrix below, we have highlighted largest plus of ones having size 17.

We start by creating four auxiliary matrices left[][], right[][], top[][], bottom[][] where 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 cell (i, j) including cell (i, j) respectively by using Dynamic Programming

if grid[i][j] == 1
left[i][j] = left[i][j – 1] + 1

if grid[i][j] == 1
top[i][j] = top[i – 1][j] + 1;

if grid[i][j] == 1
bottom[i][j] = bottom[i + 1][j] + 1;

if grid[i][j] == 1
right[i][j] = right[i][j + 1] + 1;

After calculating above matrices, we find the cell (i, j) that has maximum value in each direction (by considering minimum of left[i][j], right[i][j], top[i][j], bottom[i][j] ).

## C

Output:

Largest Plus of 1’s has size of 17

## Java

Output:

Largest Plus of 1’s has size of 17

The time complexity of above solution is O(N*N) and auxiliary space used by the program is O(N*N).

(3 votes, average: 5.00 out of 5)