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
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
@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
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 gobind@gmail.com wrote:
Hi,
Solution is available athttp://geeksforgeeks.org/?p=6257
--
You received
ravi is right ..
http://alexeigor.wikidot.com/kadane
On Wed, Dec 8, 2010 at 7:31 PM, Prims topcode...@gmail.com 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,
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 =
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
@ashish: I should try your solution.
On Oct 10, 3: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]{if ( $key = substr (0, 6,
@ ashish agarwal
ur solution will not work on this :
10101
0
1
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)
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.comwrote:
@ ashish agarwal
ur solution will not work on this :
10101
0
1
11000
On Oct 10, 6:59 pm, ashish agarwal ashish.cooldude...@gmail.com
can u plz xplain??
On Thu, Oct 7, 2010 at 2:32 PM, Chi c...@linuxdna.com 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 mallesh...@gmail.com wrote:
Largest Rectangle in a Matrix:
Given
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 techrascal...@gmail.com wrote:
can u plz xplain??
On Thu, Oct 7, 2010 at 2:32 PM, Chi c...@linuxdna.com
12 matches
Mail list logo
