Course4all

Set Matrix Zeroes

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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]]
  1. copy = [[1, 0], [1, 1]]
  2. Find 0 at (0, 1)
  3. In copy: Set row 0 to 0s, col 1 to 0s.
  4. copy becomes [[0, 0], [1, 0]]
  5. 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 FlagsCol Flagsi, jAction
[F, T, F][F, T, F]1, 1matrix[1][1]=0, so row[1]=T, col[1]=T
[F, T, F][F, T, F]0, 1row[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.
  1. Use two variables row0 and col0 to track if the first row and column themselves need to be zeroed.
  2. Iterate through the rest of the matrix, and if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
  3. 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));
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionFind All Duplicates in an Array
Next Question →Maximum Sum of Two Non-Overlapping Subarrays