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.

Practice

1. What is the main goal of the Set Matrix Zeroes In Place problem?

easy

A. Count the number of zero elements in the matrix.

B. Find the sum of all elements in the matrix.

C. Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space.

D. Sort each row of the matrix in ascending order.

Solution

1. Step 1: Understand the problem requirement

   The problem asks to change the matrix so that any row or column containing a zero should be set entirely to zero.

2. Step 2: Note the constraint of in-place modification

   The matrix must be modified without using extra space for another matrix or large data structures.

3. Final Answer:

   Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space. -> Option C

4. Quick Check:

   Set matrix zeroes in place = Modify matrix rows and columns with zeros [OK]

Hint: Remember: zero means zero entire row and column [OK]

Common Mistakes:

• Using extra space like another matrix
• Only zeroing rows or only columns
• Not modifying the matrix in place

2. Which of the following C code snippets correctly declares a 3x3 matrix to be used for the Set Matrix Zeroes problem?

easy

A. int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};

B. int matrix[3] = {1,2,3,4,5,6,7,8,9};

C. int matrix[][] = {{1,2,3},{4,5,6},{7,8,9}};

D. int matrix[3][3] = {1,2,3,4,5,6,7,8};

Solution

1. Step 1: Check correct 2D array declaration syntax in C

   In C, a 2D array must have fixed sizes for both dimensions, and initialization uses nested braces.

2. Step 2: Validate each option

   int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}}; correctly declares and initializes a 3x3 matrix. int matrix[3] = {1,2,3,4,5,6,7,8,9}; is a 1D array with too many elements. int matrix[][] = {{1,2,3},{4,5,6},{7,8,9}}; misses size for second dimension. int matrix[3][3] = {1,2,3,4,5,6,7,8}; has too few initializers (matrix[2][2] uninitialized).

3. Final Answer:

   int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}}; -> Option A

4. Quick Check:

   Correct 2D array syntax = int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}}; [OK]

Hint: Use nested braces for 2D array initialization [OK]

Common Mistakes:

• Missing size for second dimension
• Using 1D array for 2D data
• Incorrect initializer braces

3. What will be the matrix after running the in-place zeroing algorithm on this 3x3 matrix?

int matrix[3][3] = {
  {1, 0, 3},
  {4, 5, 6},
  {7, 8, 9}
};

medium

A. [[1, 0, 3], [4, 5, 6], [7, 8, 9]]

B. [[0, 0, 0], [4, 0, 6], [7, 0, 9]]

C. [[0, 0, 0], [0, 0, 0], [7, 0, 9]]

D. [[0, 0, 0], [4, 5, 6], [0, 0, 0]]

Solution

1. Step 1: Identify zero positions in original matrix

   Zero is at position (0,1). So row 0 and column 1 must be zeroed.

2. Step 2: Set entire row 0 and column 1 to zero

   Row 0 becomes [0,0,0]. Column 1 elements at rows 1 and 2 become 0, so matrix[1][1]=0 and matrix[2][1]=0.

3. Final Answer:

   [[0, 0, 0], [4, 0, 6], [7, 0, 9]] -> Option B

4. Quick Check:

   Zero at (0,1) zeroes row 0 and col 1 = [[0, 0, 0], [4, 0, 6], [7, 0, 9]] [OK]

Hint: Zero row and column of each zero element [OK]

Common Mistakes:

• Zeroing entire matrix
• Missing zeroing column elements
• Not zeroing row elements

4. Consider this code snippet for setting matrix zeroes in place. What is the main bug?

void setZeroes(int matrix[3][3]) {
  int i, j;
  for(i=0; i<3; i++) {
    for(j=0; j<3; j++) {
      if(matrix[i][j] == 0) {
        for(int k=0; k<3; k++) {
          matrix[i][k] = 0;
          matrix[k][j] = 0;
        }
      }
    }
  }
}

medium

A. It uses wrong loop bounds causing out-of-bounds access.

B. It does not check for zeros at all.

C. It uses extra space which is not allowed.

D. It modifies zeros immediately causing cascading zeroing and incorrect results.

Solution

1. Step 1: Analyze immediate zeroing inside nested loops

   The code sets zeros immediately when it finds a zero, which changes matrix during iteration.

2. Step 2: Understand cascading zeroing problem

   New zeros created cause further zeroing in the same pass, leading to incorrect results.

3. Final Answer:

   It modifies zeros immediately causing cascading zeroing and incorrect results. -> Option D

4. Quick Check:

   Immediate zeroing causes cascading errors = It modifies zeros immediately causing cascading zeroing and incorrect results. [OK]

Hint: Mark zeros first, then update matrix after [OK]

Common Mistakes:

• Zeroing matrix while scanning
• Not separating marking and updating steps
• Assuming immediate zeroing is safe

5. Given a 4x4 matrix:

int matrix[4][4] = {
  {1, 2, 3, 4},
  {5, 0, 7, 8},
  {9, 10, 11, 12},
  {0, 14, 15, 16}
};

Which is the correct matrix after applying the optimal in-place zeroing algorithm using first row and column as markers?

hard

A. [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]]

B. [[1, 0, 3, 4], [0, 0, 0, 0], [9, 0, 11, 12], [0, 0, 0, 0]]

C. [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

D. [[1, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12], [0, 14, 15, 16]]

Solution

1. Step 1: Identify zero positions

   Zeros at (1,1) and (3,0).

2. Step 2: Determine first row and first column zero flags

   First row: no zeros (firstRowZero = false). First column: zero at (3,0) (firstColZero = true).

3. Step 3: Mark zeros using first row and column (inner matrix)

   Scan i=1 to 3, j=1 to 3: (1,1)=0 sets matrix[1][0]=0, matrix[0][1]=0.

4. Step 4: Zero inner matrix using marks

   For i=1 to 3, j=1 to 3: if matrix[i][0]==0 or matrix[0][j]==0, set matrix[i][j]=0. Zeros row 1 (mark at [1][0]), col 1 (mark at [0][1]), row 3 (orig [3][0]=0).

5. Step 5: Apply flags to borders

   First row unchanged (false). First col all zeroed (true): matrix[0][0]=0, matrix[2][0]=0 (among others).

6. Final Answer:

   [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] -> Option A

7. Quick Check:

   Zeros at (1,1),(3,0) zero rows 1&3, cols 0&1 = [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] [OK]

Hint: Use first row/column as zero markers to save space [OK]

Common Mistakes:

• Zeroing entire first row or column incorrectly
• Not marking zeros properly
• Overwriting markers too early