I wrote a simple program to this job
It will not use the extra space but it will take (m*n) time
It will store mark the elements with -1 first and then make it zero
it will work for any array size arr[2*2] to arr[n*n]
-----------------------------
Sample code
main()
{
int arr[4][4] = {1, 1, 1,1,
1, 1, 1,1,
1, 1, 0,1,
1,1,1,1 };
int i,j,k,l,m,n;
m = 4;
n = 4;
printf("Original Array\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%d",arr[i][j]);
}
printf("\n");
}
//Algorithm
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j] == 0)
{
k =0;
while(k<m)
{
arr[k][j] = -1;
k++;
}
l =0;
while(l<n)
{
arr[i][l] = -1;
l++;
}
}
}
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j] == -1)
arr[i][j] = 0;
}
}
printf("Modified Array\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%d",arr[i][j]);
}
printf("\n");
}
}
-----------------------------
On Nov 27, 3:22 pm, "chandra kumar" <[EMAIL PROTECTED]>
wrote:
> Hi,
> If we are about to use an extra space this would be a better solution
>
> say the array is
>
> * # * * * * *
> * # X X X *
> * # X X X *
> * # X X X *
> **
> * *Now in the above array use the fields containing *** to set the required
> columns to zero and *#* to set the required rows to zero. *Thus we are using
> one extra space for the first row.* And the key thing to note is for any
> (i,j) that we are scanning we are going to set (0,j) and (i,0) to *0* and we
> are not going to scan these fileds later. (i.e.) say we are now at (5,8) we
> are going to change to fields at (0,8) and (5,0) which we would have seen or
> scanned already so making it *0* is not going to affect our scanning.
>
> Thanks and Regards,
> K.V.Chandra Kumar.
>
> On 27/11/2007, James Fang <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > Here I come up with a better solution.
>
> > first I need 2 auxiliary link list, named Rows and Cols, in where the
> > "contains zero column/row" is stored.
>
> > then I scan the matrix, when finding an '0', I just insert the row and
> > column of this '0' into the Rows and Cols lists.
>
> > then after the first scan, tranverse the Rows and Cols lists, clear
> > all the Rows and Cols in the list to zero.
>
> > Best Regards,
> > James Fang
>
> > On 11月27日, 上午12时50分, "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 < <mailto:[EMAIL PROTECTED]
> > > dave_and_da...
> > > @juno.com> 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 -- 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
-~----------~----~----~----~------~----~------~--~---
