Algorithm for finding the largest area of a rectangle in a given boolean array
So the question itself is pretty simple, each input, I am given a width and height, both do not exceed 200, and then row 0 and 1s to represent a 2D plane.
Like this.
4 5
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
The goal is to find the area to the right, with area 12. Needless to say, rectangles can only be 1s.
I was thinking about flooding at the time of writing this, but it had to reevaluate for every 1s in the array. What's the optimal algorithm for this?
source to share
The best algorithm I can think of is to traverse the 2D matrix and, starting at one corner, top left, backwards, bottom right corner in this case, do the following:
For each 1 found, find the longest horizontal line of 1 as well as the vertical one. For efficiency, the position to the right has one less than 1 than the one to the left of it (you should still get your vertical maximum); you just restart the counter every time you press 0. The same goes for the next line.
The product of two numbers is the maximum possible area of the rectangle, starting from this position. In another data structure, store the position, maxWidth and maxHeight and order based on the area with the largest area on top. Avoid placing subrectangles for efficiency; you can do this by ignoring the right adjacent 1 with a maxHeight that is less than or equal to its own value. I leave the choice of data structure to you.
Now you are looking at the data structure you created and start at the maximum rectangle. find the closest 0. You will divide the rectangle into 2 sub-lines that exclude the horizontal line where 0 is, and 2 sub-lines that exclude the vertical line where 0 is. In case 0 is on the edge, you will only get 3 sub-lines and if it is in the corner, then only 2. Delete the rectangle, insert the newly created sub-elements and keep the largest order of the regions. Now repeat this process with the next rectangle from the data structure until you find a rectangle without a 0. This is the largest.
This should be more efficient than checking all possible submatrices.
source to share
similar to the following problem: find the submatrix that has the highest sum. this can be done with an O (n ^ 3) algorithm. i believe you can find it on stackoverflow or internet search.
for this problem, u can replace 0s with -INF and then apply the above algorithm to find the largest area of the rectangle.
source to share
There are several comments pointing to an answer with linear complexity, but I thought I wanted to mention what seems like a simple O (n ^ 2) algorithm.
For each cell, calculate the number of those that lie both completely below it and entirely to the left of it. You can do this in linear time by working in rows at the bottom left, looking at the cell below it and at the subtotal of the cells on the left.
A rectangle can be defined by a point in the lower left corner and a point in the upper right corner. These are, of course, four corners. If you add the previously calculated totals for the bottom left and top right and subtract the totals for the top left and bottom right, you get the number of cells in the rectangle - cells outside the rectangle are either never counted at all, or discarded. Exactly where this rectangle depends on what you do in corner cases, and exactly how you interpret "all the way down to it and all the way to the left". However, given the two corners that define the rectangle, you can calculate the amount within it by extracting four numbers and doing addition and subtraction.
With a rectangle defined by two points, O (n ^ 2) rectangles need to be considered (since I'm taking n as the data size, which means there are O (n) points in the search area). Since I can compute the sum in each rectangle at constant time, and discard those that have no sum, which means all points are covered, the total cost is O (n ^ 2).
source to share
/*
Given a 2D binary array(2D array of 0 and 1's) with m rows and n columns,find area of largest sub-array(rectangle)
consisting entirely of 1's.
*/
public int findMaxRectangleArea(int[][] A,int m,int n){
// m=rows & n=cols according to question
int[] single;
int largeX = 0,largest = 0;
for (int i = 0; i < m; i++) {
single = new int[n]; //one d array used to check line by line & it size will be n
for (int k = i; k < m; k++) { // this is used for to run until i contains element
int a = 0;
int y = k - i + 1; // is used for row and col of the comming array
int shrt = 0,ii = 0,small = 0;
int mix = 0;
int findX = 0;
for (int j = 0; j < n; j++) {
single[j] = single[j] + A[k][j]; // postions element are added
if (single[j] == y) { //element position equals
shrt = (a == 0) ? j : shrt; //shortcut
a=a+1;
if (a > findX) {
findX = a;
mix = shrt;
}
} else {
a = 0;
}
}
a = findX;
a = (a == y) ? a - 1 : a;
if (a * y > largeX * largest) { // here i am checking the values with xy
largeX = a;
largest = y;
ii = i;
small = mix;
}
}
}// end of loop
return largeX*largest;
} //end of method
/*
Time complexity = method contains 2 inner loops so m*m & 1 outer loop n
so the complexity is-------------------> O((m^2)*n)
Space Complexity is-------it directly proportional to the size of the array i.e ---------------> (m*m)+n
*/
source to share