20 Sept 2024•C•Medium

Set Matrix Zeroes

set entire row and column to zero when element is zero, using first row and column as markers for O(1) space.

use first row and first column as markers to track which rows/columns need to be zeroed. first check if first row and column themselves need clearing, then use them to mark other cells.

for cells [1..m-1][1..n-1], if cell is zero, mark matrix[r][0] = 0 and matrix[0][c] = 0. then in second pass, clear rows/columns based on these markers. finally clear first row/column if needed.

approach

check if first row/column need clearing (store flags)
use first row/column as markers for rest of matrix
clear rows/columns based on markers
clear first row/column if flags set

complexity

O(mn) time for three passes. O(1) space using matrix itself for markers.

Solution files

C•set-matrix-zeroes/solution.c

"syntax-comment">#include <stdio.h>

void setZeroes(int **matrix, int matrixSize, int *matrixColSize) {
    if (matrixSize == 0 || matrixColSize == NULL) {
        return;
    }

    int rows = matrixSize;
    int cols = matrixColSize[0];

    int clear_first_row = 0;
    int clear_first_col = 0;

    for (int c = 0; c < cols; ++c) {
        if (matrix[0][c] == 0) {
            clear_first_row = 1;
            break;
        }
    }

    for (int r = 0; r < rows; ++r) {
        if (matrix[r][0] == 0) {
            clear_first_col = 1;
            break;
        }
    }

    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }

    for (int r = 1; r < rows; ++r) {
        if (matrix[r][0] != 0) {
            continue;
        }
        for (int c = 1; c < cols; ++c) {
            matrix[r][c] = 0;
        }
    }

    for (int c = 1; c < cols; ++c) {
        if (matrix[0][c] != 0) {
            continue;
        }
        for (int r = 1; r < rows; ++r) {
            matrix[r][c] = 0;
        }
    }

    if (clear_first_row) {
        for (int c = 0; c < cols; ++c) {
            matrix[0][c] = 0;
        }
    }

    if (clear_first_col) {
        for (int r = 0; r < rows; ++r) {
            matrix[r][0] = 0;
        }
    }
}