How to find the largest rectangle in a 2D array formed by four identical corners?

Question

Consider this array:

[
  ["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]
]

I’m trying to get the width and height of the rectangle with the largest area in this 2D array. The answer should be 8 * 4 = 32 (coordinates (1, 1), (1, 8), (4, 1) and (4, 8)), since it has the largest area with the same corners "A".

Answer 1

If we consider that:

1. Small rectangles have same probability of having 4 identical corners as big rectangles

2. A point can be a corner of as many rectangles as any other point whatever its position (N = (width-1)*(height-1))

So we confirm the intuitive algorithm: we want to look for the bigger rectangles first, which are more likely to have corners on the sides rather than in the center, and stop quickly when we find them.

Approach 1: strict ordering of rectangles by area

This solution computes the shape of big rectangles so as to look for them.

The hard part is that ordering rectangles by area is not as easy as narrowing squares or circles. Rectangles of area 12 can have shape of [1,12], [2,6], [3,4], [4,3], [6,2] or [12,1] while rectangles of area 11 can only have shape of [1,11] or [11,1].

function getGreatestRectangleStrict () {
    let hMax = tab.length - 1,
        wMax = tab[0].length - 1;
    // Search valid rectangle by decreasing area
    for (let area = (hMax+1)*(wMax+1); area >= 0; --area) {
        // Compute rectangle shapes that fit in tab with given area
        let kMax = Math.min(area, hMax + 1);
        for (let k = 1; k <= kMax ; ++k)
            if (area % k === 0) {
                let height = k - 1,
                    width = area / k - 1;
                if ( width <= wMax ) {
                    // New fitting shape found, test rectangles
                    for (let top = 0; top <= hMax - height; ++top)
                        for (let left = 0; left <= wMax - width; ++left) {
                            let bottom = top + height,
                                right = left + width,
                                a = tab[top][left];
                            if ( a === tab[bottom][left] &&
                                 a === tab[bottom][right] &&
                                 a === tab[top][right])
                                // Valid rectangle: stop search
                                return [top, left, bottom, right];
                        }
                }
            }
    }
}

It performs very well on small arrays, but not on bigger ones. I think it would need an heuristic to quickly find shapes and still stop when a solution is found.

Approach 2: Mixed efficient search

This solution looks for rectangles, and speeds up when it finds some big ones.

function getGreatestRectangleMixed () {
    let greatestArea = 0;
    let greatestRectangle = [];

    // Get horizontal pairs of corners of same color
    // and their vertical positions (y)
    let pairs = {};
    for (let k = 0; k < tab.length; ++k) {
        // Heuristic: alternately search top and bottom
        let y = ( !(k % 2) ? k/2 : tab.length - (k+1)/2);

        let line = tab[y];
        if ( line.length * Math.max(tab.length-y,y+1) < greatestArea )
            break; // Heuristic: height too small

        for (let i = 0; i < line.length - 1; ++i) {
            let color = line[i];
            for (let j = line.length - 1; j > i; --j) {
                if ( (j-i+1) * tab.length < greatestArea )
                    break; // Heuristic: width too small
                if (line[i] === line[j]) {
                    // Pair of corners found
                    let pairKey = i+" "+j;
                    let cornerPair = {
                        corners: [i,j],
                        width: j-i+1,
                        y: y
                    };
                    if (! (color in pairs) )
                        pairs[color] = {};
                    if (! (pairKey in pairs[color]) )
                        // New pair of corners found, keep only first one
                        pairs[color][pairKey] = cornerPair;
                    else {
                        // Rectangle found, check area
                        let isCurrentBottom = pairs[color][pairKey].y < cornerPair.y;
                        let top = (isCurrentBottom ? pairs[color][pairKey] : cornerPair);
                        let bottom = (isCurrentBottom ? cornerPair : pairs[color][pairKey]);
                        let area = top.width * (bottom.y - top.y + 1);
                        if (area > greatestArea) {
                            greatestArea = area;
                            greatestRectangle = [
                                [top.corners[0], top.y],
                                [top.corners[1], top.y],
                                [bottom.corners[0], bottom.y],
                                [bottom.corners[1], bottom.y]
                            ];
                        }
                    }
                }
            }
        }
    }

    return greatestRectangle;
}

This solution is a bit slower than the previous one on rectangles of the size of the OP, but more stable with bigger rectangles.

Answer 2

Just because was funny:

var l = [ 
["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]];

var squares = [];
//for each position
for (var column=0; column< l[0].length; column++) 
   for (var row=0; row< l.length ; row++ ) 
    //look for all scuares from this position:
    for (var next_column = column+1; next_column < l[0].length; next_column++ )
        if ( l[row][next_column] == l[row][column] )
            for (var next_row = row+1; next_row < l.length; next_row++)
               //if it is a square
               if (l[next_row][column] == l[row][column] && 
                   l[next_row][next_column] == l[row][column]) 
                    //annotate square
                    squares.push( [ column, row, next_column, next_row  ] );

//get areas from squares
var area_l = squares.map(function(an_square) { 
    return (an_square[2]-an_square[0]+1)*(an_square[3]-an_square[1]+1);
  });

//search for big area
var max_area_index = area_l.indexOf(Math.max(  ...area_l  ));

//here it is
console.log( squares[max_area_index] );

Result: Array(4) [1, 1, 8, 4]

Answer 3

You could get first all same letter positions in dependent arrays and iterate the array for finding the most right and bottom position. Then check if the two other point have the wanted value.

If so push the found rectangel to a temporary result set. Later sort that array or pick directly the maximum area.

var array = [["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"], ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"], ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"], ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"], ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"], ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"], ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]],
    points = {},
    rectangles = [],
    count=0;

array.forEach((a, i) => a.forEach((b, j) => (points[b] = points[b] || []).push({ j, i })));

Object
    .keys(points)
    .forEach(k => {
        points[k].slice(0,-1).forEach((p, m) => {
            var n = points[k].length,
                q;

            while (n--) {
                q = points[k][n];
                if (p.i < q.i && p.j < q.j && k === array[p.i][q.j] && k === array[q.i][p.j]) {
                    rectangles.push({ key: k, top: p.i, left: p.j, bottom: q.i, right: q.j, size: (q.i - p.i + 1) * (q.j - p.j + 1) });
                }
            }
        });
    });

rectangles.sort((a, b) => b.size - a.size);

console.log(rectangles);

.as-console-wrapper { max-height: 100% !important; top: 0; }