Set Matrix Zeroes In Place in DSA C

Mental Model

When a cell in a matrix is zero, set its entire row and column to zero without using extra space.

Analogy: Imagine a grid of light bulbs. If one bulb is off, then all bulbs in the same row and column must be turned off too, but you only have a small notebook to mark which rows and columns to turn off later.

Matrix before:
1 2 3
4 0 6
7 8 9

We mark row 1 and column 1 to turn off later.

Dry Run Walkthrough

Input: matrix = [[1,2,3],[4,0,6],[7,8,9]]

Goal: Set entire row and column to zero for each zero cell, in place without extra matrix

Step 1: Check first row and first column for zeros; mark flags

matrix:
1 2 3
4 0 6
7 8 9
flags: first_row_zero = false, first_col_zero = false

Why: We need to know if first row or column should be zeroed later

Step 2: Traverse matrix from (1,1) to mark zeros in first row and column

matrix:
1 0 3
0 0 6
7 8 9
marked first row col 1 and first col row 1

Why: Mark rows and columns to zero using first row and column as markers

Step 3: Set zeros in matrix based on markers in first row and column

matrix:
1 0 3
0 0 0
7 0 9
rows and columns zeroed except first row and col

Why: Apply zeroing to rows and columns except first row and column

Step 4: Zero first row if needed

matrix:
1 0 3
0 0 0
7 0 9
first row unchanged because first_row_zero flag was false

Why: Zero first row if it originally had zero

Step 5: Zero first column if needed

matrix:
1 0 3
0 0 0
7 0 9
first column unchanged because first_col_zero flag was false

Why: Zero first column if it originally had zero

Result:

1 0 3
0 0 0
7 0 9

Annotated Code

DSA C

#include <stdio.h>

void setZeroes(int matrix[][3], int rows, int cols) {
    int first_row_zero = 0;
    int first_col_zero = 0;

    // Check if first row has zero
    for (int j = 0; j < cols; j++) {
        if (matrix[0][j] == 0) {
            first_row_zero = 1;
            break;
        }
    }

    // Check if first column has zero
    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) {
            first_col_zero = 1;
            break;
        }
    }

    // Use first row and column as markers
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Zero rows based on markers
    for (int i = 1; i < rows; i++) {
        if (matrix[i][0] == 0) {
            for (int j = 1; j < cols; j++) {
                matrix[i][j] = 0;
            }
        }
    }

    // Zero columns based on markers
    for (int j = 1; j < cols; j++) {
        if (matrix[0][j] == 0) {
            for (int i = 1; i < rows; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // Zero first row if needed
    if (first_row_zero) {
        for (int j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }

    // Zero first column if needed
    if (first_col_zero) {
        for (int i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
}

void printMatrix(int matrix[][3], int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d", matrix[i][j]);
            if (j < cols - 1) printf(" ");
        }
        printf("\n");
    }
}

int main() {
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 0, 6},
        {7, 8, 9}
    };
    setZeroes(matrix, 3, 3);
    printMatrix(matrix, 3, 3);
    return 0;
}

for (int j = 0; j < cols; j++) { if (matrix[0][j] == 0) first_row_zero = 1; }

Check if first row contains zero to zero it later

for (int i = 0; i < rows; i++) { if (matrix[i][0] == 0) first_col_zero = 1; }

Check if first column contains zero to zero it later

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

Mark rows and columns to zero using first row and column

for (int i = 1; i < rows; i++) if (matrix[i][0] == 0) for (int j = 1; j < cols; j++) matrix[i][j] = 0;

Zero rows based on markers

for (int j = 1; j < cols; j++) if (matrix[0][j] == 0) for (int i = 1; i < rows; i++) matrix[i][j] = 0;

Zero columns based on markers

if (first_row_zero) for (int j = 0; j < cols; j++) matrix[0][j] = 0;

Zero first row if needed

if (first_col_zero) for (int i = 0; i < rows; i++) matrix[i][0] = 0;

Zero first column if needed

Output

1 0 3

0 0 0

7 0 9

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each pass is linear in matrix size

Space: O(1) because we use the matrix itself for marking without extra arrays

vs Alternative: Naive approach uses extra space O(m+n) to store zero rows and columns, this method saves space by using first row and column as markers

Edge Cases

Matrix with no zeros

Matrix remains unchanged

DSA C

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

Matrix where first row has zero

First row is zeroed at the end

DSA C

if (first_row_zero) for (int j = 0; j < cols; j++) matrix[0][j] = 0;

Matrix where first column has zero

First column is zeroed at the end

DSA C

if (first_col_zero) for (int i = 0; i < rows; i++) matrix[i][0] = 0;

When to Use This Pattern

When you need to set entire rows and columns to zero based on zero cells without extra space, use the first row and column as markers to track zero rows and columns.

Common Mistakes

Mistake: Zeroing rows and columns immediately when a zero is found, corrupting the matrix before finishing marking
Fix: First mark all zero rows and columns using first row and column, then zero them in a separate pass

Summary

Sets entire rows and columns to zero in a matrix if any cell is zero, modifying the matrix in place.

Use when you want to save space and avoid extra memory while zeroing rows and columns.

The key insight is to use the first row and first column as markers to remember which rows and columns to zero.