Leetcode: Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?1. O(m+n) space solutionAnalysis:
To achieve O(m+n) space, you need two array to store information while traversal the matrix for the first time checking if it is zero or not. You can also combine two arrays into one, but still cost O(m+n) space. So I just use two to store row and column information.
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean[] zeroRows = new boolean[matrix.length];
        boolean[] zeroCols = new boolean[matrix[0].length];
        //traversal the entire matrix to check if it is zero or not
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows[i] = true;
                    zeroCols[j] = true;
                }
            }
        }
        //now set matrix zero based on the two boolean arrays
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (zeroRows[i] || zeroCols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

2. *Optimal* O(1) space solution

Analysis:
To save space, we can just make use of the space inside the matrix. Which means, we use the first row and first column to store the information.
In the first traversal, we set the corresponding cell on the first row or first column to 0 if there is any cell which is zero in this row or column.
In the second traversal, we set the matrix to zeros based on the first row and first column.

 public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;
        //traversal the entire matrix to check if it is zero or not
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) {
                        firstRowHasZero = true;
                    }
                    if (j == 0) {
                        firstColHasZero = true;
                    }
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        //now set matrix zero based on first row and first column
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
//deal with the first column
        if (firstColHasZero) {
            for (int i = 1; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
//deal with the first row
        if (firstRowHasZero) {
            for (int i = 1; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
    }

Note: The tricky part of this algorithm is, if without those two boolean variables to keep track of if there is any zero in the first row or first column , when matrix[0][0]==0, we have no idea if the first row contains zero, or it is the first column contains zero, or both. also, we should deal with the rest part first based on the first row and first column and then deal with the first row and first column based on the two boolean values.

FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *