JAVA constant space solution (Hint: use space inside the matrix)


  • 6
    Z

    An easy way to solve this problem is to use extra O(m + n) space, storing the zero row and column indices.

    We can improve it by not using the extra O(m + n) space, instead, we can use the space inside that input matrix (inspired by Shangrila's solution, which use the first row and column for storage).

    In this solution, at the beginning, I find the first zero element, and use that row and column as the temp place for storing the other zero element indices. After we get all the zero indices, then set the corresponding row and columns to zero. Please see the code below.

    public void setZeroes(int[][] matrix) {
        int rowTemp = -1;   // select a row to store the column indices for the zero element
        int colTemp = -1;   // select a column to store the row indices for the zero element
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    // find the first zero element
                    if (rowTemp == -1) {
                        rowTemp = i;
                        colTemp = j;
                    }
                    // update indice in the row and column temp
                    else {
                        matrix[rowTemp][j] = 0;
                        matrix[i][colTemp] = 0;
                    }
                }
            }
        }
        // no zero in the matrix
        if (rowTemp == -1)
            return;
        // set rows to zero
        for (int i = 0; i < matrix.length; i++) {
            if (i == rowTemp)   // skip the temp row
                continue;
            if (matrix[i][colTemp] == 0) {
                for (int j = 0; j < matrix[0].length; j++)
                    matrix[i][j] = 0;
            }
        }
        // set columns to zero
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[rowTemp][j] == 0) {
                for (int i = 0; i < matrix.length; i++)
                    matrix[i][j] = 0;
            }
        }
        // set the final temp row to zero
        for (int j = 0; j < matrix[0].length; j++)
            matrix[rowTemp][j] = 0;
    }

Log in to reply
 

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