Set Matrix Zeros

• leetcode 73
• medium

Description

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?

Hide Company Tags: Microsoft

Hide Tags: Array

Hide Similar Problems: (M) Game of Life

Thinking

To solving this problem in place, we should use the first column and the first row to record information. "one zero, whole zero" is the condition to reduce the dimension.

Java Solution

public class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        if(n == 0) return;
        int m = matrix[0].length;
        if(m == 0) return;
        boolean firstCol = false;
        boolean firstRow = false;

        for(int i = 0; i < n; ++i){
            if(matrix[i][0] == 0){
                firstCol = true;
                break;
            }
        }

        for(int i = 0; i < m; i++){
            if(matrix[0][i] == 0){
                firstRow = true;
                break;
            }
        }

        for(int i = 1; i < n; ++i){
            for(int j = 1; j < m; ++j){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for(int i = 1; i < n; ++i){
            for(int j = 1; j < m; ++j){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        if(firstCol){
            for(int i = 0; i < n; ++i){
                matrix[i][0] = 0;
            }
        }

        if(firstRow){
            for(int i = 0; i < m; ++i){
               matrix[0][i] = 0;
            }
        }
    }
}