Set Matrix Zeroes

Problem in Plain English

Whenever a cell of an m x n matrix is zero, set its whole row and column to zero in place while using only constant extra space.

Problem Statement

Given an m x n integer matrix, if any cell holds 0, set its entire row and column to 0. The update must happen in place.

A copy of the matrix makes the logic trivial but costs m x n extra space, and two marker arrays cost m + n. Aim for a constant-space solution that still reads only the original zero positions.

Constraints

m == matrix.length
n == matrix[0].length
$1 \le m,n \le 200$
$-2^{31} \le \text{matrix[i][j]} \le 2^{31}-1$

Examples

Example 1

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

Only (1, 1) originally contains zero. Every cell in row 1 or column 1 becomes zero, while the four corners stay 1. Zeros created during the update do not trigger further changes.

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]]

The original zeros at (0, 0) and (0, 3) clear row 0 and columns 0 and 3. Columns 1 and 2 in the lower rows remain unchanged, even though the finished first row contains zeros there.

Example 3

Input: matrix = [[5, 0, -7]]
Output: [[0, 0, 0]]

The single original zero clears the only row, so every entry becomes zero. There are no interior rows; the first-row flag handles the whole update.

Example 4

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

No cell originally contains zero. Negative values are ordinary nonzero entries, so the entire matrix stays unchanged.

Intuition

Only zeros present in the original matrix may trigger changes. In Example 1, the original zero at (1, 1) clears row 1 and column 1; the newly created zero at (1, 0) must not clear column 0. Separate discovery from painting: a copy preserves the original evidence, while the optimal approach stores row and column decisions in the matrix borders and remembers the original border decisions in two flags.

Approaches

Copy Matrix

Solution Details

Reveal Copy Matrix: intuition, complexity, and code

Intuition

Zeroing cells as they are found corrupts the evidence: a newly written 0 looks like an original one and zeroes extra rows. Copying the matrix first freezes the original zero positions, so a second pass can paint rows and columns safely from the pristine copy.

Step-by-Step Logic

Make a deep copy by copying each row independently. Example 1 stores the original 3 by 3 values in orig, so future writes cannot change discovery.
Visit every coordinate in the copy. For each original zero, clear its entire row and column in the supplied matrix; do not search newly written input zeros.
Example 1 finds only (1, 1). Clearing its row changes the input to [[1, 1, 1], [0, 0, 0], [1, 1, 1]]; clearing its column produces [[1, 0, 1], [0, 0, 0], [1, 0, 1]].
Finish scanning the copy, including coordinates after the zero. None of Example 1's remaining copied entries is zero, so make no additional changes and finish without returning a new matrix.

Why It Works

The deep copy orig keeps every original cell unchanged even while the input is painted. Each original zero causes exactly its own row and column to be written to zero. A cell is therefore cleared if and only if at least one original zero shares its row or column. All other cells receive no writes and retain their original values. Repeated painting is harmless because writing zero twice has the same result as writing it once. The procedure mutates the supplied matrix and preserves its outer object and each row object.

Dry Run

Copy Matrix: variable states at each step
Stage / original coordinate	Original value	Action	Input matrix after action
Deep copy	-	orig keeps all initial values	[[1,1,1],[1,0,1],[1,1,1]]
(0,0), (0,1), (0,2), (1,0)	1 at each	no painting	[[1,1,1],[1,0,1],[1,1,1]]
(1,1)	0	set row cell (1,0) to 0	[[1,1,1],[0,0,1],[1,1,1]]
same zero	0	set row cell (1,1) to 0	[[1,1,1],[0,0,1],[1,1,1]]
same zero	0	set row cell (1,2) to 0	[[1,1,1],[0,0,0],[1,1,1]]
same zero	0	set column cell (0,1) to 0	[[1,0,1],[0,0,0],[1,1,1]]
same zero	0	set column cell (1,1) to 0	[[1,0,1],[0,0,0],[1,1,1]]
same zero	0	set column cell (2,1) to 0	[[1,0,1],[0,0,0],[1,0,1]]
(1,2), (2,0), (2,1), (2,2)	1 at each in orig	no painting, despite new input zeros	[[1,0,1],[0,0,0],[1,0,1]]
Finish	-	original matrix now holds result	[[1,0,1],[0,0,0],[1,0,1]]

Complexity Analysis

Time Complexity

O(mn(m+n))

Space Complexity

O(mn)

Let m and n be the row and column counts and z the number of original zeros. Copying and scanning cost O(mn); each original zero repeats n row writes and m column writes, giving O(mn + z(m + n)). With z = mn in an all-zero matrix, this is O(mn(m + n)), not O(mn): rows and columns can be repainted many times. The deep snapshot allocates m row arrays and mn entries, O(mn) auxiliary space because n is at least 1. The required result occupies the existing matrix; no output array or replacement rows are allocated.

Code

Solution.java

1class Solution {2    public void setZeroes(int[][] matrix) {3        int m = matrix.length;4        int n = matrix[0].length;5        // Deep-copy each row so new output zeros cannot trigger discovery.6        int[][] orig = new int[m][n];7        for (int r = 0; r < m; r++) {8            for (int c = 0; c < n; c++) {9                orig[r][c] = matrix[r][c];10            }11        }12        for (int r = 0; r < m; r++) {13            for (int c = 0; c < n; c++) {14                if (orig[r][c] == 0) {15                    for (int k = 0; k < n; k++) {16                        matrix[r][k] = 0;17                    }18                    for (int k = 0; k < m; k++) {19                        matrix[k][c] = 0;20                    }21                }22            }23        }24    }25}

Hints

Hint 1

Zeroing eagerly backfires: after you paint row 1, its new zeros look original and column 0 gets painted too.

Hint 2

Decide everything from a frozen snapshot first: a copy, or two marker arrays recording exactly which rows and columns held an original zero.

Hint 3

The first row and first column can hold those markers themselves; keep two flags for whether each of them started with a zero because the corner cell serves both.

Edge Cases

With no original zeros, every value including negative numbers remains unchanged.
A zero only in the first row, such as [[1,0],[2,3]], clears that row and column 1 but does not clear column 0: the two border flags must remain independent.
A zero only in the first column behaves symmetrically; a zero at (0,0) requires both border flags.
For a single row or single column, interior scans are empty and the original-border flags decide the result. A zero anywhere clears the sole row or column.
An all-zero 200 by 200 matrix remains zero. The copy approach still repaints each original zero's row and column, exposing its larger worst-case time.

Common Mistakes and Interview Tips

Painting zeros during the discovery scan, so freshly painted zeros trigger extra rows and columns (the cascading-zero bug).
Reusing matrix[0][0] as both border markers without flags, losing whether the first row or the first column was originally zero.
Skipping the final border pass, which leaves the first row or column unpainted when the only zero sat inside it.
Clearing the first row or column before applying all interior markers destroys which other rows or columns originally needed clearing.
Shallow-copying only the outer matrix shares its row arrays with the input, so the copy approach would discover newly created zeros.
Returning a newly constructed matrix instead of mutating the supplied one violates the void/None/undefined contract. These snippets preserve every original row object too.
Interview tip: explain the original-zero invariant and why the border flags must be captured before marking; then account for repeated painting in the copy approach's time bound.

Key Takeaway

Decisions that must rest on the original state need a snapshot: a copy, marker arrays, or — when space is tight — the matrix borders plus a few flags.