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


Download   Run Code


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 🙂

Get great deals at Amazon

Leave a Reply

Notify of