Tag Archives: pulse

Javascript Implementation of O(mn) Maximal Rectangle Algorithm

So I came across the need to solve the following problem in a recent project:

Given a M x N matrix of 1s or 0s, find the largest rectangular submatrix that consists of all 1s

It turns out that this is called theĀ maximal rectangle problem, and pops up in a surprising number of places (for example: finding the largest area / rectangle in a histogram, or in my case, for making a block-based tile puzzler). Then I needed a solution. Continue reading