Zero Out Rows and Columns Containing a Zero

Medium20–25 min

Topics

ArrayMatrix

Companies

AmazonMicrosoftGoogleFacebook

Given a matrix, if any cell contains 0, set its entire row and entire column to 0 — based on the ORIGINAL zero positions, not any zeros created along the way. The naive fix is to copy the matrix first so the original zero positions stay available while zeroing happens. But that copy costs O(rows·cols) extra space. The clever trick: the matrix's own first row and first column can double as marker storage for which rows/columns need zeroing — no extra structure needed, just two booleans to remember whether the first row/column themselves originally had a zero before they get repurposed.

Test Case 1:

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

Output:[[1,0,1],[0,0,0],[1,0,1]]

Explanation:The single zero at (1,1) wipes out all of row 1 and all of column 1.

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

Explanation:Two original zeros — at (0,0) and (0,3) — wipe out row 0 and columns 0 and 3.

Test Case 3:

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

Output:[[1,2],[3,4]]

Explanation:No zeros anywhere, so nothing changes.

Constraints

◆1 ≤ rows, cols ≤ 20
◆-100 ≤ matrix[i][j] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

matrix (rows separated by ;) — 2-5 rows, 2-5 cols

1	class Solution {
2	public int[][] setMatrixZeroes(int[][] matrix) {
3	int rows = matrix.length, cols = matrix[0].length;
4	boolean firstRowZero = false, firstColZero = false;
5	for (int j = 0; j < cols; j++) if (matrix[0][j] == 0) firstRowZero = true;
6	for (int i = 0; i < rows; i++) if (matrix[i][0] == 0) firstColZero = true;
7	for (int i = 1; i < rows; i++) {
8	for (int j = 1; j < cols; j++) {
9	if (matrix[i][j] == 0) {
10	matrix[i][0] = 0;
11	matrix[0][j] = 0;
12	}
13	}
14	}
15	for (int i = 1; i < rows; i++) {
16	for (int j = 1; j < cols; j++) {
17	if (matrix[i][0] == 0 \|\| matrix[0][j] == 0) {
18	matrix[i][j] = 0;
19	}
20	}
21	}
22	if (firstRowZero) for (int j = 0; j < cols; j++) matrix[0][j] = 0;
23	if (firstColZero) for (int i = 0; i < rows; i++) matrix[i][0] = 0;
24	return matrix;
25	}
26	}
27

Variables

firstRowZerofalse

INITIALIZE

Check row 0 for a zero, since it's about to double as marker storage: firstRowZero = false.

Step 1 / 13

Approach & Solutions

Brute Force

Brute

Copy the matrix first, so the ORIGINAL zero positions stay available even after zeroing starts. Scan the copy for zeros — whenever one is found at (i, j), zero out row i and column j in the real matrix. Checking the copy instead of the live matrix is what prevents a newly-created zero from triggering more zeroing than it should. This codebase's judge needs a return value to grade against, so — unlike the classic in-place / void version of this problem — this page's function returns the modified matrix directly.

TimeO(rows·cols)

SpaceO(rows·cols)

Java

Try it out

class Solution {
    public int[][] setMatrixZeroes(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] original = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                original[i][j] = matrix[i][j];
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (original[i][j] == 0) {
                    for (int k = 0; k < cols; k++) matrix[i][k] = 0;
                    for (int k = 0; k < rows; k++) matrix[k][j] = 0;
                }
            }
        }
        return matrix;
    }
}

Optimal — First Row/Column as Markers

Optimal

Instead of allocating a whole extra matrix, reuse the matrix's own first row and first column as marker storage — matrix[i][0] = 0 means "row i needs zeroing," and matrix[0][j] = 0 means "column j needs zeroing." Since that overwrites the first row/column's own original values, save whether THEY originally contained a zero first (firstRowZero / firstColZero), then restore that at the end.