CareerCup

Start scanning each row from top to bottom. Stop when find a '1'
Scan each row from bottom to top. Stop when u find a '1'
Scan each column from left to right and then right to left. stop when u find a '1'
This will give u the largest rectangular matrix.

This problem can make me think of multiple option strategy to relate with known problems :
Directed Graph
Dynamic programming
Determinant Strategy
- These are the one i can think on top of my head.

Best suited seems to be a Dynamic programming.

It's almost the same as another interview question from MS that I've heared about.

Some of you may have misunderstand the problem, it asks you to find the largest square matrix, whose elements are all '1'.

The trick is to use DP, and best algorithm can do it in O(M*N).

geniusxsy: can you please explain the way to go ?

for (a), halve the matrix into two pieces, so the largest square can be:
in the left region --- recursive call on the left region
in the right region --- recursive call on the right region
cross the mid separation line --- O(N*M)
So, finally:
T(N,M) = 2 * T(N/2,M) + O(N*M)
--> T(N,M) = O(N*M) assuming M is Omega(logN)

Only tricky part is, how to implement this in the O(N*M): find the largest square that crosses the mid line.

Well, it's not that difficult anyway, since O(N*M) is a pretty loose requirement.

for(b), it's a more difficult to find the largest rectangular that crosses a separation line, since rectangular has more flexibility than square. But still, you can do it in O(N*M), with more complicated code. Sorry I can't find an easy way to illustrate that without a draft paper.

1. find the largest square matrix with 1's

The largest matirx will be the original matrix itself :)

{
"A" being the original matrix
SUB[i][j] = {
A[i][j]
if (A[i][j] = 0 || SUB[i-1][j] = 0 || SUB[i][j-1] || SUB[i-1][j-1])
min(SUB[i-1][j], SUB[i][j-1], SUB[i-1][j-1]) + 1
if otherwise
}
}
Matrix SUB will give you the modified matrix with the lowest right corner of each submatrix having the count.

If Matrix(i.j) != 0 then OPT(i,j) =OPT(i, j-1) + OPT(i-1,j) -OPT(i-1, j-1) else
OPT(i,j) = 0;

So we can get it in O(m*n)

int Source[M][N]; // initial matrix
int Result[M][N]; // matrix with the result

for(int i = 0; i < M; i++) Result[i][0] = Source[i][0];
for(int j = 0; j < N; j++) Result[0][j] = Source[0][j];
for(int i = 1; i < M; i++)
{
	for(int j = 1; j < N; j++)
	{
		if(Source[i][j] == 0)
		{
			Result[i][j] = Source[i][j];
		}
		else
		{
			Result[i][j] = min(Result[i - 1][j], Result[i][j - 1], Result[i - 1][j - 1]) + 1;
		}
	}
}

Now let's Result[i_max][j_max] is the largest value in the Result matrix. Then (i_max, j_max) - indexes of the bottom right corner of the answer submatrix, and Result[i_max][j_max] is the size (dimention) of the answer submatrix.
I.e., the answer of the question is a submatrix of the Source matrix Source[i_max - Result[i_max][j_max] + 1 .. i_max][j_max - Result[i_max][j_max] + 1 .. j_max].