Back to solutions

Set Matrix Zeroes

MediumMatrix

If an element in an m x n matrix is 0, set its entire row and column to 0, in place.

Open problem
Constraints
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

First row and column as markers

Time O(m * n)Space O(1)

Use the first row and column to record which rows and columns must be zeroed, with one extra flag for the first column. Apply the marks in a second pass, then handle the first row and column last.

#include <bits/stdc++.h>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstCol = false;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstCol = true;
        for (int j = 1; j < n; j++)
            if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
    }
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 1; j--)
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        if (firstCol) matrix[i][0] = 0;
    }
}