Set Matrix Zeroes

Master this topic with zero to advance depth.

Set Matrix Zeroes

If an element is 0, we must mark its row and column. To do this in-place, we can use the first row and first column of the matrix itself as auxiliary storage (flags).

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Visual Representation

Matrix:
[1, 1, 1]
[1, 0, 1]
[1, 1, 1]

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

Medium

Examples

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
The element at (1,1) is 0, so row 1 and column 1 are set to 0.

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]]
Elements at (0,0) and (0,3) are 0, so their rows and columns are set to 0.

Approach 1

Level I: Brute Force (Extra Matrix)

Intuition

Create a copy of the matrix. If an element in the original is 0, set the entire row and column in the copy to 0. This is simple but uses O(M*N) extra space and involves redundant work.

⏱ O(M*N * (M+N)) where M and N are dimensions of the matrix.💾 O(M*N) for the copy matrix.

Detailed Dry Run

Matrix Copy Trace

matrix = [[1, 0], [1, 1]]

copy = [[1, 0], [1, 1]]
Find 0 at (0, 1)
In copy: Set row 0 to 0s, col 1 to 0s.
copy becomes [[0, 0], [1, 0]]
Update original matrix with copy values.

java

import java.util.Arrays;

public class Main {
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] copy = new int[m][n];
        for (int i = 0; i < m; i++) copy[i] = matrix[i].clone();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    for (int k = 0; k < n; k++) copy[i][k] = 0;
                    for (int k = 0; k < m; k++) copy[k][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) matrix[i] = copy[i];
    }
    public static void main(String[] args) {
        int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        setZeroes(matrix);
        System.out.println(Arrays.deepToString(matrix));
    }
}

Approach 2

Level II: Row and Column Auxiliary Arrays

Intuition

We can improve the space complexity by using two auxiliary boolean arrays: row of size m and col of size n. If matrix[i][j] == 0, we set row[i] = true and col[j] = true. Finally, we traverse the matrix again and set matrix[i][j] = 0 if row[i] or col[j] is true.

⏱ O(M*N) two passes through the matrix.💾 O(M+N) for the auxiliary arrays.

Detailed Dry Run

Row Flags	Col Flags	i, j	Action
[F, T, F]	[F, T, F]	1, 1	matrix[1][1]=0, so row[1]=T, col[1]=T
[F, T, F]	[F, T, F]	0, 1	row[0]=F, col[1]=T -> matrix[0][1]=0

java

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

Approach 3

Level III: Optimal Solution (In-place Flags)

Intuition

Use the first row and first column of the matrix itself to store flags for which rows and columns should be zeroed.

Use two variables row0 and col0 to track if the first row and column themselves need to be zeroed.
Iterate through the rest of the matrix, and if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
Finally, zero out cells based on flags, then the first row/column.

⏱ O(M*N) two passes through the matrix.💾 O(1) extra space.

Detailed Dry Run

Visual Process

matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

Initial Scan:
Found 0 at (1, 1) -> Mark First Row/Col
[1, 0, 1]  (matrix[0][1] = 0)
[0, 0, 1]  (matrix[1][0] = 0)
[1, 1, 1] 

Final Update (excluding row0/col0):
[1, 0, 1] 
[0, 0, 0] (Row 1 was marked)
[1, 0, 1] (Col 1 was marked)

java

import java.util.Arrays;

public class Main {
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        
        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 (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
        if (row0) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
    public static void main(String[] args) {
        int[][] matrix = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(matrix);
        System.out.println(Arrays.deepToString(matrix));
    }
}

← Previous QuestionFind All Duplicates in an Array

Next Question →Maximum Sum of Two Non-Overlapping Subarrays

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.