Then the case....
1 1 1
1 1 1
0 1 1
Scan I
1 1 1
1 1 1
0 1 0
Scan II
0 1 1
0 1 1
0 1 0
Scan III
0 1 1
0 1 1
0 0 0 this will the right answer, but cosidering next case, we get
Scan IV
0 1 0
0 1 0
0 0 0 but this case should not be considered here, right?
Thanks and Regards,
K.V.Chandra Kumar
On 23/11/2007, Dave <[EMAIL PROTECTED]> wrote:
>
>
> I was pretty careless with cut and paste from Case 1. Let's try Case 2
> again
> Start:
> 1 1 0
> 1 1 1
> 0 1 1
>
> After first scan:
> 1 1 0
> 1 1 1
> 0 1 0
>
> After second scan:
> 0 1 0
> 0 1 1
> 0 1 0
>
> After third scan:
> 0 0 0
> 0 1 1
> 0 1 0
>
> It looks like I need a 4th step. If the lower right element is zero,
> zero the last row and the last column.
>
> 0 0 0
> 0 1 0
> 0 1 0
>
> The simplest case which requires this missing step is
> 1 1 1
> 1 1 1
> 1 1 0
>
> which should produce
>
> 1 1 0
> 1 1 0
> 0 0 0
>
> The four-step algorithm can be streamlined slightly as follows:
>
> 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.
>
> Second, scan the last row, ignoring the last element, and zero every
> column that ends with a zero.
>
> Third, scan the last column, including the last element, and zero
> every row that ends with a zero.
>
> Finally, if the last element in the last row is zero, zero the last
> column.
>
> 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 23, 2:20 am, "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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
