Skip to content

Instantly share code, notes, and snippets.

@zed
zed / dp.py
Last active January 19, 2022 00:24
Find height, width of the largest rectangle containing all 0's in the matrix
#!/usr/bin/env python
"""Find height, width of the largest rectangle containing all 0's in the matrix.
The algorithm for `max_size()` is suggested by @j_random_hacker [1].
The algorithm for `max_rectangle_size()` is from [2].
The Python implementation [3] is dual licensed under CC BY-SA 3.0
and ISC license.
[1]: http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix#comment5169734_4671342