Set Matrix Zeroes

Problem

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

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

Python Solution

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    zero_rows, zero_cols = set(), set()
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)
    for r in range(rows):
        for c in range(cols):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0
    return matrix

C++ Solution

void setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    unordered_set<int> zeroRows, zeroCols;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                zeroRows.insert(r);
                zeroCols.insert(c);
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (zeroRows.count(r) || zeroCols.count(c)) matrix[r][c] = 0;
        }
    }
}

Java Solution

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        Set<Integer> zeroRows = new HashSet<>();
        Set<Integer> zeroCols = new HashSet<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    zeroRows.add(r);
                    zeroCols.add(c);
                }
            }
        }
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (zeroRows.contains(r) || zeroCols.contains(c)) matrix[r][c] = 0;
            }
        }
    }
}

Complexity

Time: O(m × n) — the matrix is scanned twice, once to record zero positions and once to apply them. Space: O(m + n) for the sets of zero rows and columns; this can be reduced to O(1) by using the matrix's own first row and column as markers instead.