The only square is found when s=2. Your program will look at s=3 and not find a square, so it will never find the square.
Try it and you will see what I mean.. Don On Monday, March 31, 2014 2:42:13 PM UTC-4, atul007 wrote: > > @Don: what is the point of considering s=2 when we have already found > s=3.As question says find "the maximum subsquare". Which is of size 3 and > this the expected outcome. > > > On Mon, Mar 31, 2014 at 11:28 PM, Don <[email protected] <javascript:>>wrote: > >> 000000 >> 011110 >> 010100 >> 011100 >> 010000 >> 000000 >> >> In this case, when i and j are 1, your algorithm will set s = 3. The if >> statement will fail, and it will never notice that it could have formed a >> square with s=2. >> >> Don >> >> >> On Sunday, March 30, 2014 9:49:21 AM UTC-4, atul007 wrote: >> >>> @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] <javascript:>. >> > > -- 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].
