Make delicious recipes!

Largest rectangle with border in a 2D matrix



Puzzle: Given a 2D matrix with 1s and 0s.

Find the largest rectangle in this matrix such that the border of the matrix is made up of all 1s.

Example:

0 1 0 0 0
0 1 0 0 0
1 1 1 1 0
0 1 0 1 0
0 1 1 1 0

The biggest rectangle here is from (2,1) to (4,3) with an area of 3x3 = 9


Solution: The brute force algorithm would check for all possible rectangles.

To check all rectangles formed from a given cell needs one to look at all cells on that cell's horizontal line
Corresponding to each cell on the horizontal line, one has to look at all cells on the vertical line.
Say if one is at cell (2,1), then traversal to find the rectangle would go at each cell from (2,1) to (2,4)
For each cell there, it would go from (2,k) to (4,k).
This gives only the right and down path.
To complete the rectangle, we then need to come left and then down (back to the node we started).
Thus, order of execution at each stage is O(n4) (assuming a square matrix with side n)
For the complete matrix, it becomes O(n6)

An O(n4) solution is given below which first calculates the length of longest 1-bordered lines (horizontal and vertical) at each cell.
With that information, finding a rectangle at any cell becomes an O(n2) task.
Taking all cells into account, total order of execution becomes O(n4).

Code:
/************************************************************************
 * A utility class to store:
 *   1) length of longest horizontal line (with 1s) ending at matrix[i][j]
 *   2) height of longest vertical line (with 1s) ending at matrix[i][j]
 ***********************************************************************/
class Pair
{
    public int l=0;
    public int h=0;

    public Pair(int l, int h)
    {
        super();
        this.l = l;
        this.h = h;
    }

    @Override
    public String toString()
    {
        return "(l=" + l + ", h=" + h + ")";
    }
}

/************************************************************************
 * Finds all the possible rectangles and then chooses the maximum from them
 ***********************************************************************/
public class LargestBorderedRectangle
{
    public static void main (String args[]) throws Exception
    {
        int rows = 5;
        int cols = 4;
        boolean [][] matrix = new boolean [rows][cols];
        Pair[][] endingHere;

        initMatrix(rows, cols, matrix);
        
        matrix[1][1] = true;
        matrix[1][2] = true;
        matrix[1][3] = true;
        
        matrix[2][1] = true;
        matrix[2][3] = true;
        
        matrix[3][1] = true;
        matrix[3][2] = true;
        matrix[3][3] = true;
        
        endingHere = createEndsMatrix(matrix, rows, cols);
        findLargestRectangle(endingHere, rows, cols);
        
        // Add another rectangle in the above matrix.
        matrix[0][0] = true;
        matrix[0][1] = true;
        matrix[1][0] = true;
        matrix[1][1] = true;
        
        endingHere = createEndsMatrix(matrix, rows, cols);
        findLargestRectangle(endingHere, rows, cols);
        
        // Break the smaller rectangle
        matrix[0][0] = false;

        endingHere = createEndsMatrix(matrix, rows, cols);
        findLargestRectangle(endingHere, rows, cols);
    }

    static void findLargestRectangle(Pair[][] endingHere, int rows, int cols)
    {
        int maxArea = 0;
        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<cols; j++)
            {
                Pair p = endingHere[i][j];
                if (p.l > 1 && p.h > 1)
                {
                    int h = p.h;
                    while (h > 1)
                    {
                        Pair above = endingHere[j - (h - 1)][j];
                        int l = p.l;

                        while (l>1)
                        {
                            Pair left = endingHere[i][i - (l - 1)];
                            if (above.l >= l && left.h >= h)
                            {
                                System.out.println ("Found rectangle at " + i + ", " + j);
                                if (l * h > maxArea)
                                {
                                    maxArea = l * h;
                                }
                            }
                            l--;
                        }
                        h--;
                    }
                }
            }
        }
        System.out.println ("Area of biggest rectangle with borders of 1 = "+maxArea);
    }

    static Pair[][] createEndsMatrix(boolean [][]matrix, int rows, int cols)
    {
        Pair[][] endingHere = new Pair[rows][cols];

        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<cols; j++)
            {
                if (matrix[i][j] == false)
                {
                    endingHere[i][j] = new Pair(0,0);
                }
                else
                {
                    int l = 1;
                    int h = 1;

                    if (i>0)
                    {
                        Pair above = endingHere[i-1][j];
                        h = above.h + 1;
                    }
                    if (j>0)
                    {
                        Pair left  = endingHere[i][j-1];
                        l = left.l + 1;
                    }
                    endingHere[i][j] = new Pair(l, h);
                }
            }
        }

        debugEndings(endingHere, rows, cols);
        return endingHere;
    }

    static void initMatrix(int rows, int cols, boolean[][] matrix)
    {
        for (int i=0; i<rows; i++)
            for (int j=0; j<cols; j++)
                matrix[i][j] = false;
    }

    static void debugEndings(Pair[][] endingHere, int rows, int cols)
    {
        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<cols; j++)
            {
                System.out.print(endingHere[i][j] + " ");
            }
            System.out.println();
        }
    }
}
Sample execution for 3 cases:
Output:
(l=0, h=0) (l=0, h=0) (l=0, h=0) (l=0, h=0) 
(l=0, h=0) (l=1, h=1) (l=2, h=1) (l=3, h=1) 
(l=0, h=0) (l=1, h=2) (l=0, h=0) (l=1, h=2) 
(l=0, h=0) (l=1, h=3) (l=2, h=1) (l=3, h=3) 
(l=0, h=0) (l=0, h=0) (l=0, h=0) (l=0, h=0) 
Found rectangle at 3, 3
Area of biggest rectangle having borders made of 1 = 9


(l=1, h=1) (l=2, h=1) (l=0, h=0) (l=0, h=0) 
(l=1, h=2) (l=2, h=2) (l=3, h=1) (l=4, h=1) 
(l=0, h=0) (l=1, h=3) (l=0, h=0) (l=1, h=2) 
(l=0, h=0) (l=1, h=4) (l=2, h=1) (l=3, h=3) 
(l=0, h=0) (l=0, h=0) (l=0, h=0) (l=0, h=0) 
Found rectangle at 1, 1
Found rectangle at 3, 3
Area of biggest rectangle having borders made of 1 = 9


(l=0, h=0) (l=1, h=1) (l=0, h=0) (l=0, h=0) 
(l=1, h=1) (l=2, h=2) (l=3, h=1) (l=4, h=1) 
(l=0, h=0) (l=1, h=3) (l=0, h=0) (l=1, h=2) 
(l=0, h=0) (l=1, h=4) (l=2, h=1) (l=3, h=3) 
(l=0, h=0) (l=0, h=0) (l=0, h=0) (l=0, h=0) 
Found rectangle at 3, 3
Area of biggest rectangle having borders made of 1 = 9








Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal