algorithm - Find largest rectangle containing only zeros in an N×N binary matrix -

given nxn binary matrix (containing 0's or 1's), how can go finding largest rectangle containing 0's?

example:

          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  

for above example, 6×6 binary matrix. return value in case cell 1:(2, 1) , cell 2:(4, 4). resulting sub-matrix can square or rectangular. return value can size of largest sub-matrix of 0's, in example 3 × 4.

here's solution based on "largest rectangle in histogram" problem suggested @j_random_hacker in comments:

[algorithm] works iterating through rows top bottom, each row solving this problem, "bars" in "histogram" consist of unbroken upward trails of zeros start @ current row (a column has height 0 if has 1 in current row).

the input matrix mat may arbitrary iterable e.g., file or network stream. 1 row required available @ time.

#!/usr/bin/env python collections import namedtuple operator import mul  info = namedtuple('info', 'start height')  def max_size(mat, value=0):     """find height, width of largest rectangle containing `value`'s."""     = iter(mat)     hist = [(el==value) el in next(it, [])]     max_size = max_rectangle_size(hist)     row in it:         hist = [(1+h) if el == value else 0 h, el in zip(hist, row)]         max_size = max(max_size, max_rectangle_size(hist), key=area)     return max_size  def max_rectangle_size(histogram):     """find height, width of largest rectangle fits entirely under     histogram.     """     stack = []     top = lambda: stack[-1]     max_size = (0, 0) # height, width of largest rectangle     pos = 0 # current position in histogram     pos, height in enumerate(histogram):         start = pos # position rectangle starts         while true:             if not stack or height > top().height:                 stack.append(info(start, height)) # push             elif stack , height < top().height:                 max_size = max(max_size, (top().height, (pos - top().start)),                                key=area)                 start, _ = stack.pop()                 continue             break # height == top().height goes here      pos += 1     start, height in stack:         max_size = max(max_size, (height, (pos - start)), key=area)         return max_size  def area(size):     return reduce(mul, size) 

the solution o(n), n number of elements in matrix. requires o(ncols) additional memory, ncols number of columns in matrix.

latest version tests @ https://gist.github.com/776423