@Don: the solution is very nice.. But, how can u prove that it is O(n^2).. for me it seems to be O(n^3) ..
Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2). all 1s from (n/2,0) to (n,0). On Thu, Jan 17, 2013 at 9:28 PM, Don <[email protected]> wrote: > 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 > > -- > > > --
