Hey,
You assumed that you can store *-1*, but that is not possible in a bit
array (i.e., if the question states that the array can contain either 0 or 1
and nothing more than that). But if the array can contain other numbers as
you assumed then your solution will work. But the solution that Dave
mentioned seemed to be assuming that the array cannot contain any other
element and still need not require any extra memory. That's why I'm posting
all my doubts to him. If this thread can come up with a solution like that
then it is really good.
Thanks and Regards,
K.V.Chandra Kumar.
On 26/11/2007, James Fang <[EMAIL PROTECTED]> wrote:
>
> *The below algorithm cost 3*O(m*n)+NumberOfInitialZeros*( O(m)+o(n) )*
>
> * *
>
>
> =================================================================================================================================================================
>
> No matter the array can hold other elements or not, you can always use
> auxiliary memory space to make it store more than 0&1, suppose it is a M*N
> array,
>
> initializing the auxiliary space will cost O(m*n).
>
>
>
> and the algorithm can be described as follow:
>
>
>
> for(int i=0; i<n; ++i)
>
> for(int j=0; j<m; ++j)
>
> {
>
> if( array[i][j] == 0)
>
> {
>
> for(int k=0;k<n;++k)
>
> {
>
> if( array[k][j] != 0 ) array[k][j]=-1;
>
> }
>
> for(int l=0;l<m;++l)
>
> {
>
> if( array[i][l] != 0 ) array[i][l]=-1;
>
> }
>
> array[i][j] = -1;
>
> }
>
> }
>
> for(int i=0;i<n;++i)
>
> for(int j=0;j<m;++j)
>
> if(array[i][j]==-1)
>
> array[i][j]=0;
>
>
>
> *Best Regards,** **
> ** **James Fang*
> ------------------------------
>
> *发件人:* [email protected] [mailto:[EMAIL PROTECTED] *代表
> *chandra kumar
> *发送时间:* 2007年11月23日 21:58
> *收件人:* [email protected]
> *主题:* [algogeeks] Re: NxN matrix
>
>
>
> Hi, as I understood the question goes like this (I also face this problem
> earlier)...
>
> * Given an array of 0s and 1s (whether the array can contain any other
> element apart from 0 and 1 is not mentioned in the question posted, but to
> make it hard people say that the array cannot hold element other then 0 and
> 1, basically a bit array ) . You need to change the given array such that
> each row and column that have a 0 initially should have all 0s in it.*
>
> * e.g.*
>
> * 1 1 1 1 1 **0** 1 1*
>
> * 1 0 1 1 **0 **0** 0 0*
>
> * 1 1 1 1 ====> 1 **0** 1 1*
>
> * 1 1 1 1 1 **0** 1 1*
>
>
>
> Thanks and Regards,
>
> K.V.Chandra Kumar
>
>
>
> On 23/11/2007, *MJ* <[EMAIL PROTECTED]> wrote:
>
>
> HI Chandra,
>
> As per the problem statement
>
> "Given an array of 0's and 1's whenever you encounter an 0 make
> corresponding column and row elements 0. "
>
> Does it mean make all the rows and column zero or only last row and
> column elemnt zero??
> could you reframe the problem statement with more details or an
> example.
>
> Thank YOu,
> Mayur
>
> On Nov 23, 1:20 pm, "chandra kumar" <[EMAIL PROTECTED]>
> wrote:
> > I have some questions in case 2.... questions inlined..
> >
> > Thanks and regards,
> > K.V.Chandra kumar.
> >
> > On 22/11/2007, Dave <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> >
> >
> > > Case 1
> > > Start:
> > > 0 1 1
> > > 1 1 1
> > > 1 1 1
> >
> > > After first scan:
> > > 0 1 0
> > > 1 1 1
> > > 0 1 1
> >
> > > After second scan:
> > > 0 1 0
> > > 0 1 1
> > > 0 1 1
> >
> > > After third scan:
> > > 0 0 0
> > > 0 1 1
> > > 0 1 1
> >
> > > Case 2
> > > Start:
> > > 1 1 0
> > > 1 1 1
> > > 0 1 1
> >
> > > After first scan:
> > > 0 1 0 how did we get 0 in the first row first column, we
> > > should only alter the last row and column, right?
> > > 1 1 1
> > > 0 1 0
> >
> > > After second scan:
> > > 0 0 0 how did we get these zero, only columns are to be
> > > changed, right?
> > > 0 1 1
> > > 0 0 0
> >
> > > After third scan:
> > > 0 0 0
> > > 0 1 0 how did we get this as, ast element is ignored,
> right?
> > > 0 0 0
> >
> > > Hope this helps.
> > > Dave
> >
> > > On Nov 22, 9:34 am, "chandra kumar" <[EMAIL PROTECTED]>
> > > wrote:
> > > > Hi Dave,
> > > > Can you explain your algo for these 2 cases...
> >
> > > > 0 1 1 1 1 0
> > > > 1 1 1 1 1 1
> > > > 1 1 1 0 1 1
> >
> > > > Please explain me in steps cause we tried the same problem and
> can't
> > > get
> > > > it done for without using extra space. ( we used 1 extra space, if
> the
> > > > array can contain only 0 or 1 and no other number, otherwise we
> store
> > > some
> > > > other number indicating a yet to become zero and proceed, in the
> later
> > > case
> > > > we need no extra space )
> > > > Thanks and Regards,
> > > > K.V.Chandra Kumar
> >
> > > > On 15/11/2007, Dave < [EMAIL PROTECTED]> wrote:
> >
> > > > > Scan the array. If the i,j element is zero, set the last element
> of
> > > > > row i and the last element of column j to zero. Then, scan the
> last
> > > > > row, ignoring the last element, and zero every column that ends
> with a
> > > > > zero. Similarly, scan the last column, ignoring the last element,
> and
> > > > > zero every row that ends with a zero. This touches every element
> at
> > > > > most 3 times; i.e., if the array has m rows and n columns, the
> > > > > algorithm is O(1) in space and O(m*n) in time.
> >
> > > > > Dave
> >
> > > > > On Nov 14, 1:27 pm, geekko < [EMAIL PROTECTED]> wrote:
> > > > > > Given an array of 0's and 1's whenever you encounter an 0 make
> > > > > > corresponding column and row elements 0. How could you do that
> > > > > > efficiently(minimum time and minimum space complexity)? This
> > > question
> > > > > > is taken from placementsindia.blogspot.com- Hide quoted text -
> >
> > > > - Show quoted text -- Hide quoted text -
> >
> > - Show quoted text -
>
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
