# Find 1's submatrices

In the following 0/1 matrix I'm trying to identify every largest submatrices formed by 1's as shown in the picture. Submatrices can have just one row only if they have more than 3 columns. Submatrices can have just one column only if they have more than 3 rows. Submatrices should have less than maxcol columns and maxrow rows and more than mincol and minrow. In the picture mincol=minrow=2. maxrow=maxcolumn=6. I've been searching for this problem, looks like an already studied problem but couldn't find it elsewhere.

• This might be a programming question and not strictly a math question. (Are you trying to write a program to do that..? In what language?) You might want to try stackoverflow – TastySpaceApple Apr 6 '14 at 21:03

See https://stackoverflow.com/questions/14829451/how-can-i-find-all-contiguous-submatrices/14829533#14829533 . This gives an $O(n^2)$ preprocessing time step where you first compute the number of ones in the submatrix with corners $(0,0)$ and $(a,b)$ for all $a,b$. (If you do this by going through one column at a time you can do it in $O(n^2)$ time). Then for an arbitrary submatrix you can compute the number of ones in the submatrix in constant time using the preprocessing information (see the link). So you can just search over all submatrices that fit your constraints, and if you find a submatrix of all ones then you can use its size as a bound so you can skip smaller submatrices when you continue the search. (assuming that you only want submatrices of ones that have the maximum possible number of cells)