Set Matrix Zeroes

Medium Problem 29 of 151 Java and Python

Practice on LeetCode

Problem

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

Example 1

Input: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

Example 2

Input: matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

Constraints

1 ≤ m, n ≤ 200
-2³¹ ≤ matrix[i][j] ≤ 2³¹ – 1
Follow-up: use constant extra space.

Explanation

If you zero cells as soon as you find a 0, the new zeros wipe out more rows and columns than they should. So first record which rows and columns to clear, then clear them.

The records can live inside the matrix: use the first cell of each row and column as its flag. Only the first row and first column need separate booleans, since they hold the flags.

Approach 1 · Better

Row and column flag arrays

Time O(m · n)
Space O(m + n)

Mark which rows and columns contain a zero in two boolean arrays, then zero every cell whose row or column is marked.

Scan the matrix; for each 0 at (i, j), set rows[i] and cols[j].
Scan again and set matrix[i][j] = 0 if rows[i] or cols[j].

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] rows = new boolean[m];
        boolean[] cols = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        rows, cols = set(), set()
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)
        for i in range(m):
            for j in range(n):
                if i in rows or j in cols:
                    matrix[i][j] = 0

Approach 2 · Optimal

First row and column as markers

Time O(m · n)
Space O(1)

Store the row flags in column 0 and the column flags in row 0. Remember separately whether row 0 and column 0 themselves need clearing.

Note whether the first row and the first column contain a 0.
For every other cell with a 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
For every other cell, zero it if its row marker or column marker is 0.
Finally clear the first row and/or first column if noted in step 1.

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRow = false;
        boolean firstCol = false;
        for (int j = 0; j < n; j++) {
            firstRow |= matrix[0][j] == 0;
        }
        for (int i = 0; i < m; i++) {
            firstCol |= matrix[i][0] == 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++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (firstRow) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (firstCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row = any(matrix[0][j] == 0 for j in range(n))
        first_col = any(matrix[i][0] == 0 for i in range(m))
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        if first_row:
            for j in range(n):
                matrix[0][j] = 0
        if first_col:
            for i in range(m):
                matrix[i][0] = 0

Complexity compared

Approach	Time	Space
Better Row and column flag arrays	O(m · n)	O(m + n)
Optimal First row and column as markers	O(m · n)	O(1)

Key takeaways

Record first, modify second, whenever changes would feed back into the scan.
Clear the marker row and column last, or you destroy the flags before using them.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem