Set Matrix Zeroes

medium
Arrays & HashingArrayMatrixHash Table

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

Examples

Example 1

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

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

Constraints

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Using Extra Sets

Intuition

The most straightforward approach is to first scan the matrix and record which rows and columns contain a zero. Use two sets: one for rows and one for columns. Then make a second pass through the matrix: if the current cell's row or column is in the respective set, set that cell to zero.

Algorithm

  1. Initialize two sets: zeroRows and zeroCols.
  2. Iterate through every cell of the matrix. If matrix[i][j] == 0, add i to zeroRows and j to zeroCols.
  3. Iterate through every cell again. If i is in zeroRows or j is in zeroCols, set matrix[i][j] to 0.
TimeO(m * n)SpaceO(m + n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        unordered_set<int> zeroRows, zeroCols;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows.insert(i);
                    zeroCols.insert(j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (zeroRows.count(i) || zeroCols.count(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};
Java 21
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Set<Integer> zeroRows = new HashSet<>();
        Set<Integer> zeroCols = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows.add(i);
                    zeroCols.add(j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (zeroRows.contains(i) || zeroCols.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
Python 3.12
def setZeroes(matrix: list[list[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    zero_rows = set()
    zero_cols = set()

    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_rows.add(i)
                zero_cols.add(j)

    for i in range(m):
        for j in range(n):
            if i in zero_rows or j in zero_cols:
                matrix[i][j] = 0
Go 1.26
func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    zeroRows := make(map[int]bool)
    zeroCols := make(map[int]bool)

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == 0 {
                zeroRows[i] = true
                zeroCols[j] = true
            }
        }
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if zeroRows[i] || zeroCols[j] {
                matrix[i][j] = 0
            }
        }
    }
}
Approach 2

In-Place Using First Row and Column as Markers

Intuition

To avoid extra space, use the first row and first column of the matrix itself as markers. If matrix[i][j] is 0, mark matrix[i][0] and matrix[0][j] as 0. Since the first row and column are being used as markers, we need separate boolean flags to remember whether they originally contained zeros. Then use the markers to zero out cells, and finally handle the first row and column.

Algorithm

  1. Check if the first row contains any zeros (store in a boolean flag). Do the same for the first column.
  2. Iterate through the rest of the matrix (from row 1, col 1). If matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
  3. Iterate through the matrix again (from row 1, col 1). If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.
  4. If the first row flag is true, set the entire first row to 0.
  5. If the first column flag is true, set the entire first column to 0.
TimeO(m * n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool firstRowZero = false, firstColZero = false;

        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = 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 (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
};
Java 21
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;

        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = 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 (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
}
Python 3.12
def setZeroes(matrix: list[list[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))

    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0

    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
Go 1.26
func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    firstRowZero, firstColZero := false, false

    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            firstRowZero = true
        }
    }
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColZero = true
        }
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }

    if firstRowZero {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }
    if firstColZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }
}

Frequently asked questions

What is the optimal time complexity of Set Matrix Zeroes?

The most efficient approach in this guide ("In-Place Using First Row and Column as Markers") runs in O(m * n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Set Matrix Zeroes use?

Set Matrix Zeroes is a medium-level Arrays & Hashing problem involving Array, Matrix, Hash Table. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Set Matrix Zeroes be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m + n), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Spiral Matrix

Original problem: leetcode.com

Loading editor...
Input
matrix=
[[1,1,1],[1,0,1],[1,1,1]]
Expected Output
[[1,0,1],[0,0,0],[1,0,1]]