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.

My initial attempts at figuring out my own algorithm worked in the typical sense that it worked for 90% of cases, borked on 5%, and brought Chrome to a crushing halt on the final 5% of cases. Not good.

Thankfully one particularly smart guy, David Vandevoorde, wrote a fantastic article in ’98 listing various approaches in tackling this problem, each an improvement on the last. The article’s available here, and not only provides excellent explanations but also pseudocode for implementing each solution. However, as I am incompetent I had difficulties writing the fourth listing up.

After a bit of help from the following SO question from a guy having issues implementing the optimal solution in Python I finally managed to get everything working as expected in Javascript. THE DEETS BE BELOW (Important: coord system has (0,0) at upper left of screen)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* Maximal Rectangle: (0,0) => upper-left corner */
 
/*
Given a M x N matrix of 1s & 0s, finds the largest
rectangular submatrix that consists of all 1s
 
@param int[][] matrix 2d array of 1s / 0s rep. game board 
@returns obj quad upper-left (x, y), width, height and area of max rect, {x: -1, y: -1} means no rect found)
*/
function getMaxRect(matrix){
    var bestUpperLeft = {x: -1, y: -1};
    var bestLowerRight = {x: -1, y: -1};
 
    var cache = new Array(rows+1), stack = []; // JS arrays have push and pop. Awesome!
    for(var i = 0; i < cache.length; i++)
        cache[i] = 0;
 
    for(var x = cols-1; x >= 0; x--){
        updateCache(matrix, x, cache);
        var width = 0;
        for(var y = 0; y < rows+1; y++){
            if(cache[y] > width){
                stack.push({y: y, width: width});
                width = cache[y];
            }
            if(cache[y] < width){
                while(true){
                    var pop = stack.pop();
                    var y0 = pop.y, w0 = pop.width;
                    if(((width * (y - y0)) > area(bestUpperLeft, bestLowerRight)) && (y-y0 >= minQuadY) && (width >= minQuadX)){
                        bestUpperLeft = {x: x, y: y0};
                        bestLowerRight = {x: x+width-1, y: y-1};
                    }
                    width = w0;
                    if(cache[y] >= width)
                        break;
                }
                width = cache[y];
                if(width != 0)
                    stack.push({y: y0, width: w0});
            }
        }
    }
    return { x: bestUpperLeft.x, y: bestUpperLeft.y, lenX: bestLowerRight.x-bestUpperLeft.x+1, lenY: bestLowerRight.y-bestUpperLeft.y+1, area: area(bestUpperLeft, bestLowerRight)};
}
 
/*
Finds rectangular area bounded by given upper left / lower right coords
 
@param obj upperLeft coords of upper left point
@param obj lowerRight coords of lower right point
@returns int bounded area
*/
function area(upperLeft, lowerRight){
    if(upperLeft.x > lowerRight.x || upperLeft.y > lowerRight.y)
        return 0;
    return ((lowerRight.x+1)-(upperLeft.x))*((lowerRight.y+1)-(upperLeft.y));
}
 
/*
Updates maximal rectangle algorithm cache
 
@param int[][] matrix 2d array of 1s / 0s rep. game board 
@param int x current cache column
@param int[] cache
*/
function updateCache(matrix, x, cache){
    for(var y = 0; y < rows; y++)
        if(matrix[x][y] == 1)
            cache[y]++;
        else
            cache[y] = 0;
}

And the result?

A HORRENDOUS MIX OF RANDOMLY GENERATED COLOURS

A HORRENDOUS MIX OF RANDOMLY GENERATED COLOURS

As an aside: I wanted my rectangles to have certain minimum dimensions. To enforce this constraint, change:

if(((width * (y - y0)) > area(bestUpperLeft, bestLowerRight)){

to

if(((width * (y - y0)) > area(bestUpperLeft, bestLowerRight)) && (y-y0 >= minQuadY) && (width >= minQuadX)){

where ‘minQuadY’ and ‘mindQuadX’ are the minimum height and width respectively (I know, not the best variable names).

Leave a Reply

Your email address will not be published. Required fields are marked *