Set Matrix Zeroes

The problem

You are given a grid matrix with m rows and n columns (row_count and column_count in the code). Wherever a cell holds 0, set its whole row and its whole column to 0. Change the grid in place.

Only the zeros that were there at the start count. A cell that becomes 0 because of this rule does not clear its own row and column.

Example 1

Input: matrix = [[4, 2, 7, 1], [3, 0, 5, 8], [6, 9, 2, 0]]

Output: [[4, 0, 7, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

The 0 at row 1, column 1 clears row 1 and column 1. The 0 at row 2, column 3 clears row 2 and column 3.

	c0	c1	c2	c3
r0	4	0	7	0
r1	0	0	0	0
r2	0	0	0	0

Example 2

Input: matrix = [[5, 3], [2, 0]]

Output: [[5, 0], [0, 0]]

Only the bottom row and the right column are cleared.

Example 3

Input: matrix = [[0, 6, 2]]

Output: [[0, 0, 0]]

One row: the 0 clears all of it.

Constraints

• 1 ≤ m, n ≤ 200
• −2³¹ ≤ matrix[i][j] ≤ 2³¹ − 1

Clarifying questions

Do new zeros spread further?

No. Only the zeros in the original grid clear rows and columns.

Must it be in place?

Yes. The grid itself changes. The follow-up asks for O(1) extra memory.

Can any value be used as a marker?

No. Values cover the whole 32-bit range, so there is no spare value to mean "clear me".

Is the grid square?

Not always. m and n can differ.

Spot the pattern

The danger is clearing too early: a new zero looks like an original one. So the work splits in two: first record which rows and columns to clear, then clear. The only question is where to keep the record. The grid’s own first row and first column can hold it, which is a classic in-place matrix trick.

Solutions

Full copyO(m·n·(m + n))Row and column setsO(m·n), O(m + n) spaceMarkers in the gridO(m·n), O(1) space

Show all

Full copy O(m·n·(m + n))

The idea

Copy the whole grid first. Then read the copy, cell by cell. Each time the copy has a 0, clear that row and that column in the real grid. The copy never changes, so new zeros cannot start more clearing.

It is correct and easy to see. But the copy is a full second grid, and each zero clears a whole row and column on its own, even when they overlap.

Walkthrough

	c0	c1	c2	c3
r0	4	2	7	1
r1	3	0	5	8
r2	6	9	2	0

1. copy = [row[:] for row in matrix]
2. for i in range(row_count):
3. for j in range(column_count):
4. if copy[i][j] == 0:
5. for k in range(column_count): matrix[i][k] = 0
6. for k in range(row_count): matrix[k][j] = 0

Zeroing while we read would create new zeros that wipe out more. So first copy the grid, and read only from the copy.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Full copy: read the zeros from an untouched copy, clear rows and columns in
    // the grid. Each zero clears m + n cells: O(m * n * (m + n)) time, O(m * n) memory.
    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length, columnCount = matrix[0].length;
        // New zeros must not count, so read only from a copy that never changes.
        int[][] copy = new int[rowCount][];
        for (int i = 0; i < rowCount; i++) copy[i] = matrix[i].clone();
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < columnCount; j++) {
                if (copy[i][j] != 0) continue;
                for (int k = 0; k < columnCount; k++) matrix[i][k] = 0;
                for (int k = 0; k < rowCount; k++) matrix[k][j] = 0;
            }
        }
    }
}

Big O

Time O(m·n·(m + n))Space O(m·n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The double loop reads every cell of the copy, 1 step each. Inside it, each 0 runs two more loops: n cells of its row and m cells of its column.

   1. copy = [row[:] for row in matrix]
   2. for i in range(row_count):
   3. for j in range(column_count):
   4. if copy[i][j] == 0:
   5. for k in range(column_count): matrix[i][k] = 0
   6. for k in range(row_count): matrix[k][j] = 0

2. 2 Count the runs on Example 1

   Example 1 is 3 × 4, so the copy has 12 cells to read. It has 2 zeros, and each clears 4 + 3 = 7 cells.

   12 + 2 × 7 = 26 steps.

   part	read the copy	clear for [1][1]	clear for [2][3]
   steps	12	4 + 3 = 7	4 + 3 = 7

   total

   12 + 2 × 7 = 26

3. 3 Write the count for any n

   With z zeros, the count is m·n reads plus z × (m + n) clears. In the worst case every cell is 0, so z = m·n:

   m·n + m·n × (m + n)

   Check it with Example 1: 12 + 2 × 7 = 26, with z = 2.

4. 4 Keep only the part that grows fastest

   Drop the lone m·n. The clearing part is bigger. What is left is m·n·(m + n).

   So the time is O(m·n·(m + n)).

5. S Space: count the extra memory the same way

   The copy holds all m × n cells. The space is O(m·n).

   copy (m × n cells)ijk

Row and column sets O(m·n), O(m + n) space

The idea

We do not need a whole copy, only which rows and which columns hold a 0. Pass 1 reads the grid and writes those into two sets. Pass 2 sets a cell to 0 if its row or its column is in a set.

Pass 1 never writes, so no new zero can sneak in. And each cell is cleared at most once.

Walkthrough

	c0	c1	c2	c3
r0	4	2	7	1
r1	3	0	5	8
r2	6	9	2	0

zero_rows

empty

zero_columns

empty

1. zero_rows, zero_columns = set(), set()
2. for i in range(row_count):
3. for j in range(column_count):
4. if matrix[i][j] == 0: zero_rows.add(i); zero_columns.add(j)
5. for i in range(row_count):
6. for j in range(column_count):
7. if i in zero_rows or j in zero_columns: matrix[i][j] = 0

Pass 1 only reads. It writes down which rows and which columns hold a 0.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Row and column sets: pass 1 records which rows and columns hold a 0, pass 2
    // clears. Two passes: O(m * n) time, O(m + n) memory.
    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length, columnCount = matrix[0].length;
        boolean[] zeroRows = new boolean[rowCount], zeroColumns = new boolean[columnCount];
        // Pass 1 only reads, so no new zero can be mistaken for an original.
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < columnCount; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows[i] = true;
                    zeroColumns[j] = true;
                }
            }
        }
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < columnCount; j++) {
                if (zeroRows[i] || zeroColumns[j]) matrix[i][j] = 0;
            }
        }
    }
}

Big O

Time O(m·n)Space O(m + n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each pass is a double loop over all cells. Each run does one check and maybe one set add or one write. A set lookup takes one step on average, so each run is 1 step.

   1. zero_rows, zero_columns = set(), set()
   2. for i in range(row_count):
   3. for j in range(column_count):
   4. if matrix[i][j] == 0: zero_rows.add(i); zero_columns.add(j)
   5. for i in range(row_count):
   6. for j in range(column_count):
   7. if i in zero_rows or j in zero_columns: matrix[i][j] = 0

2. 2 Count the runs on Example 1

   Example 1 has 12 cells. Pass 1 reads 12, and pass 2 visits 12.

   12 + 12 = 24 runs.

   pass	1: find zeros	2: clear
   cells	12	12

   total

   12 + 12 = 24

3. 3 Write the count for any n

   m·n + m·n = 2·m·n

   Check it with Example 1: 2 × 12 = 24.

4. 4 Keep only the part that grows fastest

   Drop the 2. What is left is m·n, the size of the grid. No answer can do better, because every cell must be looked at.

   So the time is O(m·n).

5. S Space: count the extra memory the same way

   zero_rows holds at most m numbers and zero_columns at most n. The space is O(m + n).

   zero_rows (up to m)zero_columns (up to n)ij

Markers in the grid O(m·n), O(1) space

The idea

Keep the two sets inside the grid. Row 0 is the column set: matrix[0][j] = 0 means “clear column j”. Column 0 is the row set: matrix[i][0] = 0 means “clear row i”.

Those cells hold real data too, so first save two flags: did row 0 have a 0, and did column 0 have a 0? Then:

1. For every cell outside row 0 and column 0 that is 0, set its two markers.
2. For every cell outside row 0 and column 0, clear it if its row marker or column marker is 0.
3. Clear row 0 and column 0 last, using the two flags.

Why the order matters: row 0 and column 0 hold the markers, so they must be cleared last. If they went first, a cleared marker row would make every column look marked.

Walkthrough

	c0	c1	c2	c3
r0	4	2	7	1
r1	3	0	5	8
r2	6	9	2	0

first_row_zero

false

first_column_zero

false

1. first_row_zero = 0 in matrix[0]
2. first_column_zero = any(row[0] == 0 for row in matrix)
3. for i in range(1, row_count):
4. for j in range(1, column_count):
5. if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0
6. for i in range(1, row_count):
7. for j in range(1, column_count):
8. if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0
9. if first_row_zero: set row 0 to 0
10. if first_column_zero: set column 0 to 0

Use row 0 and column 0 as the sets. A 0 in column 0 marks a row to clear, and a 0 in row 0 marks a column. They hold real data too, so first remember if they had their own zeros.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Markers in the grid: row 0 and column 0 act as the column and row sets.
    // Two passes over the cells: O(m * n) time, O(1) extra memory.
    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length, columnCount = matrix[0].length;
        // Row 0 and column 0 will hold markers, so save their own zeros first.
        boolean firstRowZero = false, firstColumnZero = false;
        for (int j = 0; j < columnCount; j++) if (matrix[0][j] == 0) firstRowZero = true;
        for (int i = 0; i < rowCount; i++) if (matrix[i][0] == 0) firstColumnZero = true;
        for (int i = 1; i < rowCount; i++) {
            for (int j = 1; j < columnCount; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < rowCount; i++) {
            for (int j = 1; j < columnCount; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        // Last, because until now they held the markers.
        if (firstRowZero) for (int j = 0; j < columnCount; j++) matrix[0][j] = 0;
        if (firstColumnZero) for (int i = 0; i < rowCount; i++) matrix[i][0] = 0;
    }
}

Big O

Time O(m·n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two double loops visit the inner cells, one check each: 1 step per run. Before them, two short loops read row 0 and column 0. After them, two short loops may clear them.

   1. first_row_zero = 0 in matrix[0]
   2. first_column_zero = any(row[0] == 0 for row in matrix)
   3. for i in range(1, row_count):
   4. for j in range(1, column_count):
   5. if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0
   6. for i in range(1, row_count):
   7. for j in range(1, column_count):
   8. if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0
   9. if first_row_zero: set row 0 to 0
   10. if first_column_zero: set column 0 to 0

2. 2 Count the runs on Example 1

   Example 1 is 3 × 4. Checking row 0 reads 4 cells and column 0 reads 3. The inner part is 2 × 3 = 6 cells, visited once to mark and once to clear. Row 0 and column 0 had no zeros, so the last step does nothing.

   4 + 3 + 6 + 6 = 19 steps.

   part	check row 0	check col 0	mark	clear	row 0 and col 0
   cells	4	3	6	6	0

   total

   4 + 3 + 6 + 6 = 19

3. 3 Write the count for any n

   n + m + 2(m − 1)(n − 1), plus up to m + n at the end

   Check it with Example 1: 4 + 3 + 2 × 6 = 19.

4. 4 Keep only the part that grows fastest

   Drop everything but 2·m·n, then drop the 2. The m and n terms are small next to m·n. What is left is m·n.

   So the time is O(m·n).

5. S Space: count the extra memory the same way

   The code keeps two flags and the loop counters. The record of which rows and columns to clear lives inside the grid. The space is O(1).

   first_row_zerofirst_column_zeroij

Common mistake

Clearing row 0 and column 0 too early

If row 0 is cleared before pass 2, every matrix[0][j] reads 0, and pass 2 clears every column. The markers must stay untouched until all other cells are done.

Tested at the limits

2,000 random grids from 1 x 1 to 5 x 5 with many zeros, including zeros in row 0 and column 0. Full copy, row and column sets, and markers in the grid gave the same answer every time.

Largest inputs	Result
A 200 x 200 grid (the most allowed), values across the whole 32-bit range, with zeros in row 0 and column 0. Markers in the grid.	0.003 s, and under 0.001 MB of extra memory: two flags and the loop counters.
The same grid. Full copy.	0.002 s, and about 0.3 MB for the copy of the grid. Markers in the grid do the same job with no copy.