@don : According to question we want to find "the maximum subsquare". can you give me test case for which this wont work?
On Fri, Mar 28, 2014 at 9:41 PM, Don <[email protected]> wrote: > No, that is not the same. > It won't find a square smaller than s. > Don > > > On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote: > >> @Don : your algo time complexity is O(n^2) >> >> It can be reduced to this :- >> >> // Now look for largest square with top left corner at (i,j) >> for(i = 0; i < n; ++i) >> for(j = 0; j < n; ++j) >> { >> s = Min(countRight[i][j], countDown[i][j]); >> if (countRight[i][j] && countDown[i][j] && >> (countRight[i+s][j] >= s) && (countDown[i][j+s] >= s) && s>max) >> { >> bestI = i; bestJ = j; max = s; >> } >> } >> >> On 1/25/13, Don <[email protected]> wrote: >> > The worst case I know of is when the matrix is solid black except for >> > the lower right quadrant. In this case, it does break down into O(n^3) >> > runtime. It took about 8 times as long to run n=4000 as it took for >> > n=2000. >> > Don >> > >> > On Jan 24, 10:29 am, Don <[email protected]> wrote: >> >> I'm not sure I understand your case. However, I stated that there are >> >> cases where it is worse than O(N^2). The runtime is highly dependent >> >> on the contents of the matrix. In many cases it takes fewer than N^2 >> >> iterations. Occasionally it takes more. On average it seems to be >> >> roughly O(N^2), but again that depends a lot on what is in the matrix. >> >> I got that result by trying different ways of filling the matrix. I >> >> tried things like randomly setting each pixel with various >> >> probabilities, placing random horizontal and vertical segments, >> >> placing random squares, or placing random filled squares. I did all of >> >> those both in black on white and white on black. In all of those >> >> cases, going from n=1000 to n=2000 resulted in a runtime increase of >> >> less than a factor of 4. >> >> >> >> Don >> >> >> >> On Jan 23, 10:33 pm, bharat b <[email protected]> wrote: >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> > @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 >> >> >> >> > > -- >> > >> > -- >> > >> > >> > >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
