Question

link

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

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?

Stats

Frequency 5
Difficulty 3
Adjusted Difficulty 3
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very borning question. The O(m+n) space solution is trivial, I will not cover. The constant space solution is making use of 1st row and 1st columns of the input array.

Solution

The idea is clear enough, but writing the code is not as easy. This post is a good explanation and code for the solution.

Difficult point: when there’s 0, set 0; but when there is no 0, do not touch on the value (if original it’s 3, keep it 3).

Code

public void setZeroes(int[][] matrix) {
    int m = matrix.length;
    if (m == 0) return;
    int n = matrix[0].length;
    if (n == 0) return;

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