73. Set Matrix Zeroes

LeetCode

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }

        for (int r : rows) Arrays.fill(matrix[r], 0);
        for (int c : cols) for (int i = 0; i < m; i++) matrix[i][c] = 0;
    }
}

Remarks:

  1. TC: $O(m\times n)$, SC: $O(m + n)$.
  2. Use HashSet to avoid processing duplicatie rows/columns.

Marking Array

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
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRow = false, firstCol = false;

        // Check if first column has a zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) { firstCol = true; break; }
        }

        // Check if first row has a zero
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) { firstRow = true; break; }
        }

        // Use first row/col as markers
        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;
                }
            }
        }

        // Zero rows based on markers
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) Arrays.fill(matrix[i], 0);
        }

        // Zero cols based on markers
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < m; i++) matrix[i][j] = 0;
            }
        }

        // Finally handle first row/col
        if (firstRow) Arrays.fill(matrix[0], 0);
        if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

Remarks:

  1. TC: $O(mn)$, SC: $O(1)$.
  2. We use the first row and first column as markers, so no need for extra array to record. Good for space complexity.