Leetcode and Lintcode

Set Matrix Zeroes

Problem:

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

Have you met this question in a real interview? Yes
Example
Given a matrix

[
  [1,2],
  [0,3]
],
return [ [0,2], [0,0] ]

Challenge
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?

Solution:

The first method used two boolean arrays to store the columns or rows should be set to zero.
To make it use constant space, the second method use the first row and column to store the information that rows and columns should be set to zero.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*************************************************************************
	> File Name: SetMatrixZeros.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Sun 15 Nov 16:11:35 2015
 ************************************************************************/

public class SetMatrixZeros{
    // Solution 1, time complexity O(m * n), space complexity O(m + n)
    public void setZeroes(int[][] matrix) {
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        
        boolean[] zeroRows = new boolean[rowLength];
        boolean[] zeroCols = new boolean[colLength];

        for (int row = 0; row < rowLength; row++){
            for (int col = 0; col < colLength; col++){
                if (matrix[row][col] == 0){
                    zeroRows[row] = true;
                    zeroCols[col] = true;
                }
            }
        }

        for (int row = 0; row < zeroRows.length; row++){
            if (zeroRows[row]){
                for (int col = 0; col< colLength; col++)
                    matrix[row][col] = 0;
            }
        }

        for (int col = 0; col < zeroCols.length; col++){
            if (zeroCols[col]){
                for (int row = 0; row < rowLength; row++)
                    matrix[row][col] = 0;
            }
        }
    }

    // Solution 2, time complexity O(m * n), space complexity O(1)
    public void setZeroes(int[][] matrix) {
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // Check whether the first row contains zero
        for (int col = 0; col < colLength; col ++){
            if (matrix[0][col] == 0){
                firstRowZero = true;
                break;
            }
        }
        
        // Check whether the first column contains zero
        for (int row = 0; row < rowLength; row++){
            if (matrix[row][0] == 0){
                firstColZero = true;
                break;
            }
        }
        
        // set the element in the first row or column to 
        //  be zero if the corresponding column or row contains zero
        for (int row = 1; row < rowLength; row++){
            for (int col = 1; col < colLength; col ++){
                if (matrix[row][col] == 0){
                    matrix[0][col] = 0;
                    matrix[row][0] = 0;
                }
            }
        }
        
        // Set corresponding rows to be zeors;
        for (int row = 1; row < rowLength; row++){
            if (matrix[row][0] == 0){
                for (int col = 1; col < colLength; col ++){
                    matrix[row][col] = 0;
                }
            }
        }
        
        // Set corresponding cols to be zeros
        for (int col = 1; col < colLength; col++){
            if (matrix[0][col] == 0){
                for (int row = 1; row < rowLength; row ++){
                    matrix[row][col] = 0;
                }
            }
        }
        
        // Process the first row
        if (firstRowZero){
            for (int col = 0; col < colLength; col ++){
                matrix[0][col] = 0;
            }
        }
        
        // Process the first column
        if (firstColZero){
            for (int row = 0; row < rowLength; row++){
                matrix[row][0] = 0;
            }
        }
    }
}