Find largest rectangle containing all zero's in an N X N binary matrix
Posted
by Rajendra
on Stack Overflow
See other posts from Stack Overflow
or by Rajendra
Published on 2010-03-19T15:24:11Z
Indexed on
2010/03/19
15:31 UTC
Read the original article
Hit count: 715
Given an N X N binary matrix (containing only 0's or 1's). How can we go about finding largest rectangle containing all 0's?
Example:
I
0 0 0 0 1 0
0 0 1 0 0 1
II->0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 1 <--IV
0 0 1 0 0 0
IV
is a 6 X 6 binary matrix, return value in this case will be Cell 1: (2, 1) and Cell 2: (4, 4). Resulting sub-matrix can be square or rectangle. Return value can be size of the largest sub-matrix of all 0's also, for example, here 3 X 4.
© Stack Overflow or respective owner
