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();
}
}
}
Got a thought to share or found a bug in the code? We'd love to hear from you:
