CODEWITHSUNDEEP
c++calgorithmmatrix
SuperCoder
SuperCoder

Reputation: 121

In a matrix put 0 in the row and column of a cell which contains 0 without using extra space

Given a matrix, if a cell contains 0, then we have make entire row and column corresponding to the cell as 0. For example, if

      1 2 3
M  =  0 4 5
      4 2 0

then the output should be 

      0 2 0
      0 0 0
      0 0 0

The method I thought is as follows

  1. Make auxiliary arrays row[] and col[]. If a cell(i,j) contains 0 then, mark row[i] and col[j] as 0.(Initially row[] and col[] contains all 1s).
  2. Again traverse the whole matrix, if for cell(i,j), either of row[i] or col[j] is 0, then put cell(i,j) as 0.

This takes O(m*n) time and O(m+n) space.

How to optimize it further specially in terms of space.Any suggestions for improving time complexity are also welcomed.

Upvotes: 5

Views: 5595

Answers (6)

Mahmood Salah
Mahmood Salah

Reputation: 1

Simple and easy answer: <2 nested loop> to search through all columns and rows you find any cell = 0 through all column and set it to zeros through all row and set it to zeros. let me know if it not clear to record video for it. 

Int main()
{
//example matrix dimension rows(r=6) * columns (c=3)
int r = 6;
int c = 3;
int matrix[r][c];

for(int i=0; i<r; ++i){
    for(int j=0 ; j < c ; ++j){
        if(matrix[i][j] == 0){ 
            for(int ii=0; ii<r; ++ii){
                Matrix[ii][j] = 0 ;
            }
            for(int jj=0; jj<c; ++jj){
                Matrix[i][jj] = 0 ;
            }
       }
   }  
}
}

Upvotes: 0

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is an algorithm can do it in O(M*N) time and O(1) space : -

  1. Find the max element in the matrix .
  2. Mat[i][j] = max - Mat[i][j] for all (i,j)
  3. Notice that Mat[i][j] will only have positive values.
  4. Use negetive values as sentinels and Mat[i][j] = max as zeros.
  5. Retrieve original values as Mat[i][j] = max - Mat[i][j]

Upvotes: 0

Liu Ameng
Liu Ameng

Reputation: 150

Aha, this is an old question.

  1. Use one boolean variate(isZeroInFirstRow) saving if first row has zero element(s) or not and one boolean variate(isZeroInFirstCol) saving if first column has zero element(s) or not.

  2. Then, traverse the whole matrix. If cell(i,j)==0, then set cell(0,j) and cell(i,0) to 0.

  3. Traverse the first row of the matrix. If cell(0,j)==0, then set all elements in column(j) to 0.

  4. Traverse the first column of the matrix. If cell(i,0)==0, then set all elements in row(i) to 0.

  5. If isZeroInFirstRow==true, set all elements in row(0) to 0.

  6. If isZeroInFirstCol==true, set all elements in column(0) to 0.

Upvotes: 10

Michael Burr
Michael Burr

Reputation: 340218

You can use your algorithm without allocating and auxiliary row or column by searching the matirx for a row that contains no zeros and a column that contains no zero elements.

If either of these searches fails, then the resulting matrix will all zeros, so your work is done by simply setting all elements to zero.

Otherwise, use the row and colum you found as the bookkeeping row and column you mentioned, setting the corresponding element to zero as you find zeros in the remainder of the matrix. Once that pass is done you walk the bookkeeping row, setting the matix columns to zeros for any zero found in the bookkeeping row, similarly for the aux column.

Upvotes: 0

Massimiliano
Massimiliano

Reputation: 8032

If you are concerned with storage you may think of using some sparse matrix storage formats to store the resulting matrix, and then free the original dense input.

An example of what I am proposing may be the following (implementing COO format) which should take O(M*N) time:

#include<vector>
#include<iostream>
#include<algorithm>
#include<cstddef>

using namespace std;

int main()
{
    constexpr size_t M = 3;
    constexpr size_t N = 3;
    int matrix[M][N] = {
        {1, 2, 3},
        {0, 4, 5},
        {4, 2, 0}
    };    

    vector<size_t> markedRows;
    vector<size_t> markedColumns;
    // Search for zeroes
    for (size_t ii = 0; ii < M; ++ii) {
        for(size_t jj = 0; jj < N; ++jj) {
            if (matrix[ii][jj] == 0) {
                markedRows.push_back   (ii);
                markedColumns.push_back(jj);
            }
        }
    }
    // Sort columns (rows are ordered by construction)
    sort(markedColumns.begin(),markedColumns.end());
    // Eliminate duplicates
    markedRows.erase   (unique(markedRows.begin()   ,markedRows.end())   ,markedRows.end()   );
    markedColumns.erase(unique(markedColumns.begin(),markedColumns.end()),markedColumns.end());

    // Construct COO matrix format
    vector<size_t> irow;
    vector<size_t> icol;
    vector<int>    val;        
    for (size_t ii = 0; ii < M; ++ii) {
        for(size_t jj = 0; jj < N; ++jj) {
            if ( ( find(markedRows.begin()   ,markedRows.end()   ,ii) == markedRows.end()    ) &&
                 ( find(markedColumns.begin(),markedColumns.end(),jj) == markedColumns.end() )
                ) {
                  irow.push_back(ii);
                  icol.push_back(jj);
                  val.push_back (matrix[ii][jj]);
                }
        }
    }    
    // FROM HERE YOU NO LONGER NEED MATRIX, AND YOU CAN FREE THE STORAGE

    // Print non zero entries
    for( size_t ii = 0; ii < irow.size(); ++ii) {
      cout << "A["<<irow[ii]<<","<<icol[ii]<<"] = "<<val[ii]<<endl;   
    }


    return 0;
}

Upvotes: 1

Maroun
Maroun

Reputation: 95968

You can solve this in O(1) space. One solution is to iterate on the matrix, for each 0 you see, you fill the corresponding row/col with some character, 'X' for example.

When you finish, you should have something like that:

    X 2 X
M=  0 X X
    X X 0

Then you iterate again on the matrix and replace each 'X' with 0 to get:

    0 2 0
M=  0 0 0
    0 0 0

Upvotes: 1

Related Questions