Set Matrix Zeros

Problem

Given an m × n integer matrix, if a cell is 0 set its entire row and column to 0. Do it in place with O(1) extra space if possible.

Constraints

• 1 ≤ m, n ≤ 200

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def setZeroes(self, matrix):
        rows, cols = set(), set()
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                if v == 0:
                    rows.add(i); cols.add(j)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in rows or j in cols:
                    matrix[i][j] = 0
        return matrix

Java

class Solution {
    public void setZeroes(int[][] m) {
        int rows = m.length, cols = m[0].length;
        boolean firstRow = false, firstCol = false;
        for (int i = 0; i < rows; i++) if (m[i][0] == 0) firstCol = true;
        for (int j = 0; j < cols; j++) if (m[0][j] == 0) firstRow = true;
        for (int i = 1; i < rows; i++)
            for (int j = 1; j < cols; j++)
                if (m[i][j] == 0) { m[i][0] = 0; m[0][j] = 0; }
        for (int i = 1; i < rows; i++)
            for (int j = 1; j < cols; j++)
                if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
        if (firstRow) for (int j = 0; j < cols; j++) m[0][j] = 0;
        if (firstCol) for (int i = 0; i < rows; i++) m[i][0] = 0;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.