Zero the rows and columns containing zero elements

 

Question

   Another popular interview question is, zero the columns and rows which contain element value equal to zero.The trick here and question should be clear that,

• you should not lose the columns where zero is present while erasing the rows
• If either rows or columns is containing zero value, both of these rows & columns must be set to zero

Answer

  If the above problems in zeroing is clear, then the solution is almost visible. We just need to create an bool array to hold whether the zero is present at some index of row and some index of column.

  Just record the location where zero is present in row bool array and column where zero present in column bool array.

  After finding this, we can simple zero the row’s where flag is set and columns where the flag is set.

Code

void slashZero(int**& arr, int M, int N)

{

    bool *arr_rows = (bool*) calloc(M, sizeof(bool));

    bool *arr_col = (bool*) calloc(N, sizeof(bool));

    for(int i=0; i < M; i++) {

        for(int j=0; j < N; j++) {

            if(arr[i][j] == 0) {

                if(arr_rows[i] != true)

                    arr_rows[i] = true;

                if(arr_col[j] != true)

                    arr_col[j] = true;

            }

        }

        //zero rows

        if(arr_rows[i]) {

            for(int j=0; j < N; j++)

                arr[i][j] = 0;

        }

    }

    // zero colums

    for(int j =0; j < N ; j++) {

        if(arr_col[j]) {

            for(int i =0; i < M; i++) {

                arr[i][j] = 0;

            }

        }

    }

}

void printArray(int** arr, int M, int N)

{

    for(int i=0;i<M;i++) {

        for(int j=0;j<N;j++)

            std::cout<<arr[i][j]<<" ";

        std::cout<<std::endl;

    }

}

void main()

{

    int M=3, N=4;

    int c=1;

    int **A = (int**)calloc(M, sizeof(int*));

    for(int i=0; i<M; i++) {

        A[i] = (int*) calloc(N, sizeof(int));

        for(int j=0; j<N; j++) {

            A[i][j] = c++;

        }

    }

    A[0][1] = 0; A[1][1]=0; A[0][3]=0;

    printArray(A, M, N);

    slashZero(A, M, N);

    printArray(A, M, N);

}

Important points

• Since we can zero the rows after recording the column zero’s, we have started zeroing early. But its not necessary
• Instead of zero'ing column and rows seperately, we can zero both in one shot, using another for(i = 0->M) & for (j = 0->N) loop. We need to zero elements if either rows_bool[i] is true or columns_bool[j] is true.
• The above code is easily digestible and guessable at first run. But takes more or almost equal time if the above N2 loop is done