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
1
11000
it will be
10101
11100
12211
12000
now here if (3,1) is considered, there there is a 2
You may check the following page:
http://e-maxx.ru/algo/maximum_zero_submatrix.
It is in Russian, however it contains code in C++. Also you may try to
translate it in English.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this gr
@juver++ : Could you please elaborate your answer a little ... ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsub
There is a O(n*m) simple solution using stacks
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.
this is asnwered here
http://groups.google.com/group/algogeeks/browse_thread/thread/84b94e7527805334/fb1378d5744e0208?lnk=gst&q=rectangle+binary+matrix#fb1378d5744e0208
On Dec 8, 7:29 pm, Aditya Agrawal wrote:
> ravi is right ..http://alexeigor.wikidot.com/kadane
>
> On Wed, Dec 8, 2010 at 7:31
ravi is right ..
http://alexeigor.wikidot.com/kadane
On Wed, Dec 8, 2010 at 7:31 PM, Prims wrote:
> Hello Gobind
>
> The link contains the solution for finding the largest square in a
> binary matrix which is not valid in case of largest rectangle.
>
> -Prims
>
> On Dec 8, 6:38 pm, GOBIND KUMAR
Hello Gobind
The link contains the solution for finding the largest square in a
binary matrix which is not valid in case of largest rectangle.
-Prims
On Dec 8, 6:38 pm, GOBIND KUMAR wrote:
> Hi,
> Solution is available athttp://geeksforgeeks.org/?p=6257
--
You received this message becaus
ohh..I think my solution will work on square not on rectangles.
On Sun, Oct 10, 2010 at 8:13 PM, Mridul Malpani wrote:
> @ ashish agarwal
>
> ur solution will not work on this :
>
> 10101
> 0
> 1
> 11000
>
>
> On Oct 10, 6:59 pm, ashish agarwal
> wrote:
> > This question was asked in goo
@ ashish agarwal
ur solution will not work on this :
10101
0
1
11000
On Oct 10, 6:59 pm, ashish agarwal
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][
@ashish: I should try your solution.
On Oct 10, 3:59 pm, ashish agarwal
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]{if ( $key = substr (0, 6,
"123123121212" )
> p[i][j
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
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 =
@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algog
Can u explain z-curve?wat data structure can be used .plz provide a
link to learn thatthanks in advance
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe f
AFAIK there is an O(n^3) solution to this problem. anybody with a O(n^2)
or O(n) solution??
Mukesh Gupta
Delhi College of Engineering
On Thu, Oct 7, 2010 at 3:32 PM, tech rascal wrote:
> can u plz xplain??
>
>
> On Thu, Oct 7, 2010 at 2:32 PM, Chi wrote:
>
>> Travers the matrix in z-cu
can u plz xplain??
On Thu, Oct 7, 2010 at 2:32 PM, Chi wrote:
> Travers the matrix in z-curve or hilbert-curve. This is a heuristic
> algo. Thus you can find largest square matrix.
>
> On Oct 7, 10:39 am, malli wrote:
> > Largest Rectangle in a Matrix:
> >
> > Given an n by n matrix with zeros
Travers the matrix in z-curve or hilbert-curve. This is a heuristic
algo. Thus you can find largest square matrix.
On Oct 7, 10:39 am, malli wrote:
> Largest Rectangle in a Matrix:
>
> Given an n by n matrix with zeros and ones, find the largest sub-
> matrix full of ones in linear time. I was t
17 matches
Mail list logo
