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.

 
Largest Plus

 


 

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

Download   Run Code

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).
 

 
Author: Aditya Goel

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz