@ atul and saurabh
Here is my code of what m trying to implement .
here starting at bottom right corner we try to come up moving row by row .
in end b matrix contain's dimention of rectangle which can be formed
from Aij in Bij (width,height)
plz.. post what u make of it... can it be improved
@atul
Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)
On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@atul
read it ..
@atul..plz tell me an example for square matrix...actually i faced it first
tym...it executes...but explain plz..
On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@atul
Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5
@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:
@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..
On
@atul
1) it won't work for large dimention's coz their is a limit to size of
array we can declare on stack.
( which is typically 10^6 as far as i know :-) ).
2) the algo i m trying to find would work in linear time. while this one is
more then O(n^2)
fo rvery very large input this algo
@rahul
may be this will help you..
/* Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n) sol [ possible but we need to know tucker matrix, etc advanced
set theory's]
*/
#includeiostream
On 3/15/12, Sourabh Singh singhsourab...@gmail.com wrote:
@rahul
may be this will help you..
/* Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n) sol [ possible but we need to know
@sourabhThere are O(n^2) elements in the matrix of size nXn. Yes
we can find patterns in a substring with n elements in O(n) but can
you do that in O(sqrt(n)) (To complete your analogy),
Beside's can you allocate a 10^6X10^6 matrix in an array?
On 3/15/12, saurabh singh saurab...@gmail.com
@Sourabh : here we are talking abt 2 different problems in this post..which
are little bit similar.
1) original question says find max subset of matix contaning '1' and '0'
we knw recurrence to solve this problem , as posted above.
2) now your question is to find max subset of matrix which
April 4, 2010
Given a binary matrix, find out the maximum size square sub-matrix with all
1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
here is the recurrence for solving this
R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] ) );
On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma rahul23111...@gmail.comwrote:
April 4, 2010
Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
wats d logic behind this???
On Tue, Mar 13, 2012 at 11:59 AM, atul anand atul.87fri...@gmail.comwrote:
here is the recurrence for solving this
R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] )
);
On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
@ ALL
finding square matrix is quite a standard question and nw an easy one as
everyone knows the reccussence atul has given.
but i wanted to find max rectangle..
i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..
1. aproach
@ Sourabh: check solution i have posted in below link
http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@ ALL
@atul
read it ..
it's good but more or less like the histogram algo.. i wanted a DP.
approach..
here is some of wat i heard from a senior in colg..
1. at every index we can keep 4 variable
ht: height of max rectangle possible at index above current
wt width
Suggest an algorithm guyzzz.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
--
You received this message because you are subscribed to the Google Groups
i dint get...you should provide more details , if it is all 1 then whole
matrix is a max square..
anyways equation to find max sub square is this.
M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] )
On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
Its a square matrix containing 0s and 1s.
Will u plz elaborate about this equation ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Tue, Jan 10, 2012 at 8:36 AM,
18 matches
Mail list logo
