how do we work for a rectangle here..
the only way i could think of is once we have found a square, backtrack from
right bottom towards left and up to see if the value is not changing
10101
11100
11111
11000
it will be
10101
11100
12211
12000
now here if (3,1) is considered, there there is a 2(same as (3,1)) at (2,1)
implying that this is 3*2 rectangle(if 1,1 had been 2 also then it would
have been a 4*2 rectangle...
similarly for position(2,2), (2,1) is 2 hence this ia a 2*3 rectangle...
any other thoughts?
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Oct 11, 2010 at 11:15 AM, ashish agarwal <
ashish.cooldude...@gmail.com> wrote:
> ohh..I think my solution will work on square not on rectangles.
>
> On Sun, Oct 10, 2010 at 8:13 PM, Mridul Malpani
> <malpanimri...@gmail.com>wrote:
>
>> @ ashish agarwal
>>
>> ur solution will not work on this :
>>
>> 10101
>> 00000
>> 11111
>> 11000
>>
>>
>> On Oct 10, 6:59 pm, ashish agarwal <ashish.cooldude...@gmail.com>
>> wrote:
>> > This question was asked in google interview
>> > one solution for this question is DP
>> > make a matrix p (all rows and columns are initialized to zero)
>> > if(a[i][j]==1]{
>> > p[i][j]=min(p[i-1][j],p[i,j-1],p[i-1][j-1]]+1;}
>> >
>> > else p[i][j]=0;
>> > f
>> > find p[i][j] such that its has max value.
>> >
>> > On Sun, Oct 10, 2010 at 7:13 PM, Chi <c...@linuxdna.com> wrote:
>> > > Nevermind. I don't think Z-curve is a good solution for this problem.
>> > > This question was asked before, and somebody wrote a much simplier
>> > > solution. I wanted to show you only the quadtree or spatialindex. If
>> > > you have a quadtree-Key like this: 123123121212
>> >
>> > > You can make a query like this: if ( $key = substr (0, 6,
>> > > "123123121212" ) then ... this will query all subsquares from index
>> > > "123123xxxxx". It is used by Google Maps and Microsoft Maps.
>> >
>> > > The problem with the quadtree is that overlapping square, or
>> > > rectangle would not be found.
>> >
>> > > From Wikipedia:
>> >
>> > > >The resulting ordering can equivalently be described as the order one
>> > > would get from a depth-first traversal of a quadtree; because of its
>> close
>> > > connection with quadtrees, the Z-ordering can >be used to efficiently
>> > > construct quadtrees and related higher dimensional data structures
>> >
>> > > >http://en.wikipedia.org/wiki/Z-order_%28curve%29
>> >
>> > >http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-.
>> ..
>> >
>> > > On Oct 10, 2:04 pm, Harshal <hc4...@gmail.com> wrote:
>> > > > @Chi
>> > > > pls provide a link to learn z-curve implementation in such
>> problems....
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com<
>> algogeeks%2bunsubscr...@googlegroups.com>
>> > > .
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
