@sourabh....There 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> wrote:
> 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 tucker matrix, etc
>> advanced
>> set theory's]
>> */
>>
>>
>> #include<iostream>
>> #include<conio.h>
>>
>> int b[6][6];
>> using namespace std;
>> main()
>> { int i,j,t;
>> int a[6][6]=
>> { 0,0,0,1,0,1,
>> 0,1,1,1,0,0,
>> 1,1,1,1,0,1,
>> 0,1,1,1,1,0,
>> 1,0,0,1,0,0,
>> 0,1,0,1,1,0,};
>> for(i=0;i<6;i++)
>> for(j=0;j<6;j++)
>> { if(a[i][j]==1)
>> {
>>
>> b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
>> }
>> else
>> b[i][j]=0;
>> }
>> for(i=0;i<6;i++)
>> { for(j=0;j<6;j++)
>> { printf(" %d",a[i][j]);
>> }
>> printf("\n");
>> }
>> printf("\n\n\n\n\n");
>> for(i=0;i<6;i++)
>> { for(j=0;j<6;j++)
>> { printf(" %d",b[i][j]);
>> }
>> printf("\n");
>> }
>> getch();
>> return 0;
>> }
>>
>>
>> On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh
>> <singhsourab...@gmail.com>wrote:
>>
>>> @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 would be very very slow.. making
>>> it impractial..
>>>
>>> ( it's like if u can find substring's in linear time then why use an
>>> O(n^2) algo ;-) )
>>>
>>> NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit
>>> short
>>> on time to check implemention of your algo right now )
>>>
>>>
>>>
>>> On Wed, Mar 14, 2012 at 9:07 AM, atul anand
>>> <atul.87fri...@gmail.com>wrote:
>>>
>>>> @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 Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
>>>>> <singhsourab...@gmail.com
>>>>> > wrote:
>>>>>
>>>>>> @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.com> wrote:
>>>>>>
>>>>>>> @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 " " " " "
>>>>>>> " "
>>>>>>> hl:height of max rectangle possible at index left of current
>>>>>>> wl: " " " " "
>>>>>>> " "
>>>>>>>
>>>>>>>
>>>>>>> now problem is which one to take for current... index
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Mar 13, 2012 at 10:52 AM, atul anand
>>>>>>> <atul.87fri...@gmail.com>wrote:
>>>>>>>
>>>>>>>> @ Sourabh: check solution i have posted in below link
>>>>>>>>
>>>>>>>>
>>>>>>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh <
>>>>>>>> singhsourab...@gmail.com> wrote:
>>>>>>>>
>>>>>>>>> @ 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 is simple to keep track of max rectangle which can be
>>>>>>>>> formed from any point taking that point as top left corner of max
>>>>>>>>> rectangle and
>>>>>>>>> proceed further down .
>>>>>>>>>
>>>>>>>>> can someone suggest how can be proceed further..
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> [ NOTE: problem occurs mainly when their are more than one
>>>>>>>>> rectangles which can be formed from same point ]
>>>>>>>>>
>>>>>>>>> plz.. don't suggest the histogram method it's just a dirty way of
>>>>>>>>> avoiding to work on getting this DP right. :-)
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Mon, Mar 12, 2012 at 11:29 PM, atul anand <
>>>>>>>>> atul.87fri...@gmail.com> wrote:
>>>>>>>>>
>>>>>>>>>> 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.com> wrote:
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> 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
>>>>>>>>>>>
>>>>>>>>>>> 1 1 1
>>>>>>>>>>> 1 1 1
>>>>>>>>>>> 1 1 1
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> 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.
>>>>>
>>>> --
>>>> 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.
>>
>>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT
> blog:geekinessthecoolway.blogspot.com
>
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
--
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.
