[Solved] In a square matrix, where each cell is black or white. Design an algorithm to find the max white sub-square [closed]

Question

First note that your solution is NOT O(n^2), it is more like O(n^4), because for each cell, you look for the largest matrix that can be of size up to O(n^2) itself, so it is totalling to O(n^4).

It can be done however in O(n^2):

First, define 2 auxillary functions (implemented as matrices):

whitesLeft(x,y) = number of adjacent white cells on the same row to the left from x,y - exclusive of x,y
whitesUp(x,y) = number of adjacent white cells on the same column up from x,y -  exclusive of x,y

Now, define the recursive function:

D(0,y) = 0     if (0,y) is black
         1     otherwise
D(x,0) = 0     if (x,0) is black
         1     otherwise
D(x,y) = 0                                                         if  x,y is black
         min{ D(x-1,y-1), whitesLeft(x,y), whitesUp(x,y) } + 1     otherwise

The idea is to calculate with D(x,y) the biggest square that ends (bottom right) in (x,y). This square is calculated by finding the minimal cells to the left, cells to the up and submatrix that ends at (x-1,y-1) that has only white cells.

Note that D(x,y) can be calculated efficiently with Dynamic Programming in O(n^2), and the pre-processing to calculate the auxillary functions (matrices) is also O(n^2).

When you are done, post prcess D to find the largest value of D(x,y) for any (x,y) to get the result – this is also O(n^2).

Accepted Answer