CareerCup

any ideas? dynamic programming?

array as in row wise or column wise or both

the biggest array i found in above question is 4x4 i think?

Has any one has solution for this?

how can there be a solution when the question is not 100% clear .. what 6x2? the largest one so far seems to be 4x4.. or it is row wise or column wise.. too ambiguous..especially when th 6x2 confused people even more.

you guys read the question too fast:
0 => white
1 => black

Well I don't know but does DFS give an hint by choosing bottom as the left node and right as the right node.

Don't worry about 4x4 or 6x2 being ambiguous. Just solve the problem and get the largest continuous subarray. If there are two such subarrays, return any one of them. Now solve it.

no clue. I think it's dp. but I am not good on dp.

Here Anonymous is right!! with the question one cannot tell whether 6x2 is greater or 4x4. according to me 4x4 should be greater as it has more blacks than 6x2

You can track the "largest black block" on its top-left for each node.
For example in the given matrix, the largest block for A[4][4] is: 3X3, and the largest block for A[5][3] is: 6X1, then A[5][4] will know its largest block is: 4X2.

Denote M[i][j][0] and M[i][j][1] as the height and width of the largest block starting from (i,j). Then we have:
if A[i][j]=0, M[i][j][0]=M[i][j][1]=0, otherwise:
M[i][j][0] = min{M[i+1][j][0], M[i][j+1][0], M[i+1][j+1][0]} + 1;
M[i][j][1] = min{M[i+1][j][1], M[i][j+1][1], M[i+1][j+1][1]} + 1;

And we initialize the DP procedure by calculating the M's for the last column and last row.

Dynamic Solution will take O(n^3) time but you can solve this problem O( n^2) time.

Hi folks,

For me the above problem seems to be reducible to two-dimensional maximum sum sub-array problem. Kadanes Algorithm is the best known solution for this

http://alexeigor.wikidot.com/kadane

Any comments??

(1) Construct a new n x n matrix m, whose elements m[i][j] = number of continuous 1 to the right. This matrix can be constructed in O(n^2) time.
(2) For each m[i][j], we find the longest continuous nonzero subarray started at m[i][j] within the i-th column. The length of this subarray and the minimum of this subarray is the height and the width of the continuous block of 1 started at (i,j). This step can be done in O(n^2) too.

(3) Switch the role of row and column and repeat (1) and (2). This step is needed because the steps(1) and (2) will find the blocks along the vertical direction first. For instance, lets consider
1 1 1
1 0 0
0 0 0
the steps (1)-(2) will return the (1,1) pattern along the vertical direction for the (0,0) element.

Kadane's 2D algorithm definitely solves in O(n^3) time. However, here is another O(n^3) solution:

for (i = 0; i < n; i++)
{
	array[n] <- m[i];
	for (j = i + 1; j < n; j++)
	{
		array[n] <- array[n] & m[j]
		foreach contiguous 1's
		{
			number of ones <- (j - i) * number_of_contiguous_ones;
			if (number_of_contiguous_ones > max)
				max <- number_of_contiguous_ones
		}
	}
}

Kadane's 2D algorithm cannot solve the problem. The subarray returned by the algorithm may have one or more 0's in it.

We can solve the problem in O(n^2) :D. It requires a very clever idea though