@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 <dondod...@gmail.com> 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 <dond...@gmail.com> 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 <dondod...@gmail.com> 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 <bagana.bharatku...@gmail.com> 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 <dondod...@gmail.com> 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 <amritsa...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
>
--
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 algogeeks+unsubscr...@googlegroups.com.
