The downside is that it uses a bunch of extra space. The upside is that it is pretty fast. It only does the time-consuming task of scanning the matrix for contiguous pixels once, it only searches for squares larger than what it has already found, and it doesn't look in places where such squares could not be. In practice it performs at O(n^2) or better for most inputs I tried. But if you are devious you can come up with an input which takes longer. Don
On Jan 17, 10:14 am, marti <[email protected]> wrote: > awesome solution Don . Thanks. > > > > > > > > On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote: > > > Imagine there is a square matrix with n x n cells. Each cell is either > > filled with a black pixel or a white pixel. Design an algorithm to find the > > maximum subsquare such that all four borders are filled with black pixels; > > optimize the algorithm as much as possible --
