C solution, in-place, O(n*m) runtime, O(1) space, no recursion


  • 0
    E

    We can't just greedily search for all the zeroes and clear out their rows and columns as we go, because we need a way to differentiate between the zeroes that were originally in the matrix, and the zeroes we used to overwrite the cells we had already visited.

    The key here is recognizing that we can find the first '0' element in the matrix and re-purpose its row and column as "metadata" storage - that is, to tell us whether a particular row or column need to be cleared, before actually doing so.

    We declare some variables:
    int i, j, meta_i = -1, meta_j = -1;

    First, we scan the matrix to locate the first 0 cell, storing its location to meta_i and meta_j. If we don't find a 0 cell at all, we terminate early.

        /*
         * Find the first zero, and repurpose its row and column
         * for metadata storage 
         */
        for (i = 0; i < row_size; i++) {
            for (j = 0; j < col_size; j++) {
                if (matrix[i][j] == 0) {
                    meta_i = i;
                    meta_j = j;
                    break;
                }
            }
    
            if (meta_j != -1)  /* If zero found, bail from outer loop.*/
                break;
        }
    
        /* If we found no zero cells, we have nothing to do */
        if (meta_j == -1)
            return;
    

    Now, we walk all cells in the matrix (except for the row and column designated for metadata), and look for all the other zeroes. If a zero is found, we make a note of its location by zeroing out the corresponding cells of the metadata row and column, which we will use later. It is important to note that the metadata row/column may have had zeroes of their own, so we use '0' to mark the metadata row/column to avoid having to perform a special pass just for the metadata row/column.

        for (i = 0; i < row_size; i++) {
            for (j = 0; j < col_size; j++) {
                if (i != meta_i && j != meta_j && matrix[i][j] == 0) {
                    matrix[meta_i][j] = 0;
                    matrix[i][meta_j] = 0;
                }
            }
        }
    

    Now that we have zeroed the metadata cells corresponding to the rows and columns that need to be cleared, we iterate over the metadata column, zeroing out any any rows that we marked earlier. We must be careful to avoid clearing the metadata row itself, since it contains column-clearing information that we still need.

        for (i = 0; i < row_size; i++) {
            if (i != meta_i && matrix[i][meta_j] == 0)  /* Avoid stomping over the metadata row, since we'll need it to process columns */
                for (j = 0; j < col_size; j++)
                    if (j != meta_j)
                        matrix[i][j] = 0;
        }
    

    Similarly, we walk the metadata row, clearing out any columns that we have marked earlier. This time, we do NOT avoid stomping the metadata column, since we've already processed all the rows.

            if (matrix[meta_i][j] == 0)
                for (i = 0; i < row_size; i++)
                    matrix[i][j] = 0;
        }
    

    And now that we've used the metadata row and column to clear out our matrix, we finish by clearing out the metadata row, since we've already taken action on the information stored in it.

        /* Finally, clean up our metadata row, which we avoided stomping earlier */
        for (j = 0; j < col_size; j++)
            matrix[meta_i][j] = 0;
    

    And that's all there is to it. The complete solution is as follows.

    void setZeroes(int** matrix, int row_size, int col_size) {
        int i, j;
        int meta_i = -1, meta_j = -1;
        
        /* Find the first zero, and repurpose its row and column for metadata storage */
        for (i = 0; i < row_size; i++) {
            for (j = 0; j < col_size; j++) {
                if (matrix[i][j] == 0) {
                    meta_i = i;
                    meta_j = j;
                    break;
                }
            }
    
            if (meta_j != -1)
                break;
        }
    
        /* No zeroes */
        if (meta_j == -1)
            return;
    
        /* Process meta_i and meta_j separately */
        for (i = 0; i < row_size; i++) {
            for (j = 0; j < col_size; j++) {
                if (i != meta_i && j != meta_j && matrix[i][j] == 0) {
                    matrix[meta_i][j] = 0;
                    matrix[i][meta_j] = 0;
                }
            }
        }
    
        for (i = 0; i < row_size; i++) {
            if (i != meta_i && matrix[i][meta_j] == 0)  /* Avoid stomping over the metadata row, since we'll need it to process columns */
                for (j = 0; j < col_size; j++)
                    if (j != meta_j)
                        matrix[i][j] = 0;
        }
    
        for (j = 0; j < col_size; j++) {
            if (matrix[meta_i][j] == 0)
                for (i = 0; i < row_size; i++)
                    matrix[i][j] = 0;
        }
    
        /* Finally, clean up our metadata row, which we avoided stomping earlier */
        for (j = 0; j < col_size; j++)
            matrix[meta_i][j] = 0;
    }
    
    
    • evilwombat

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.