So the question itself is quite simple, each input, I am given a width and height, both won't exceed 200, and then a series of 0 and 1s to represent the 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 at the right, with an area of 12. Needless to say, rectangles can only be consisted of 1s.
I was thinking about flood-fill while writing this, but it would have to reevaluate for each 1s in the array. What's the optimal algorithm for this?
similar to the following problem: find the sub-matrix which has the largest sum. this can be done by an O(n^3) algorithm. i believe u can find it on stackoverflow or search on the internet.
for this problem, u can replace 0s with -INF, and then apply the above algorithm to find the largest rectangle area.
The best algorithm I can think of is to traverse the 2D matrix and starting from one corner, top left, to the facing one, bottom right in this case, do the following:
For every 1 you find, find the longest horizontal string of 1s as well as the vertical one. For efficiency, the position to the right has one less 1 than the one to its left (you still have to get its vertical maximum); you just restart the count every time you hit a 0. Same applies when you get to the next line.
The product of the two numbers is the maximum possible area for the rectangle starting at that position. In another data structure, store the position, maxWidth, and maxHeight and make the order based on area with largest area on top. Avoid placing subrectangles for efficiency; you can do this by ignoring a right-adjacent 1 with a maxHeight less than or equal to its own value. I leave the choice of the data structure up to you.
Now you go through the data structure you created and start with the max rectangle. find the nearest 0. You split the rectangle into 2 subrectangles that exclude the horizontal line where the 0 is in and 2 subrectangles that exclude the vertical line where the 0 is in. If the 0 is on the edge, you will get only 3 subrectangles and if it's in a corner, only 2. Remove the rectangle, insert the newly created subrectangles and maintain the largest area order. Now repeat this process with the next rectangle from the data structure until you find a rectangle with no 0s. That's the biggest one.
This should be more efficient than checking every possible submatrix.
There are a couple of comments pointing to answer with linear complexity, but I thought I'd mention what seems to be a simple O(n^2) algorithm.
For each cell, compute the number of ones which lie both entirely beneath it and entirely to its left. You can do this in linear time by working in rows from the bottom left, looking at the cell below it and at a subtotal from the cells to its left.
A rectangle can be defined by the point at its bottom left and the point at its top right. It has, of course, four corners. If you add the previously computed totals for the bottom left and top right, and subtract the total for the top left and bottom right, you will get the number of cells in a rectangle - the cells outside the rectangle are either never counted at all or get cancelled out. Exactly where that rectangle is depends what you do at corner cases and exactly how you interpret "entirely beneath it and entirely to its left". However, given the two corners defining a rectangle you can count the sum within it by retrieving four numbers and doing addition and subtraction.
With a rectangle defined by two points there are O(n^2) rectangles to consider (since I take n to be the size of the data, which means that the area to be searched has O(n) points). Since I can compute the sum within each rectangle in constant time and discard those that don't have a sum that means all of the points are covered, the total cost is O(n^2).
/*
Given a 2D binary array(2D array of 0's 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's 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's directly proportional to the size of the array i.e ---------------> (m*m)+n
*/
