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 lights where if one light goes off, the entire row and column of lights must also turn off, but you only have one chance to mark which rows and columns to turn off without extra notes.

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

We want to mark row 2 and column 2 to zero out 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, modifying matrix in place without extra space.

Step 1: Check first row and first column for zeros to remember if they need zeroing later

matrix:
1 2 3
4 0 6
7 8 9
firstRowZero = false, firstColZero = false

Why: We need to know if first row or column should be zeroed at the end because we will use them as markers.

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
firstRowZero = false, firstColZero = false

Why: Mark row 1 and column 1 as zero because matrix[1][1] is zero.

Step 3: Use marks in first row and column to set zeros in inner matrix

matrix:
1 0 3
0 0 0
7 0 9
firstRowZero = false, firstColZero = false

Why: Set row 1 and column 1 to zero based on markers.

Step 4: Zero out first row if needed (not needed here)

matrix:
1 0 3
0 0 0
7 0 9
firstRowZero = false

Why: First row has no zero originally, so no change.

Step 5: Zero out first column if needed (not needed here)

matrix:
1 0 3
0 0 0
7 0 9
firstColZero = false

Why: First column has no zero originally, so no change.

Result:

Final matrix:
1 0 3
0 0 0
7 0 9

Annotated Code

DSA C#

using System;

class Solution {
    public void SetZeroes(int[][] matrix) {
        int rows = matrix.Length;
        int cols = matrix[0].Length;

        bool firstRowZero = false;
        bool firstColZero = false;

        // Check if first row has zero
        for (int c = 0; c < cols; c++) {
            if (matrix[0][c] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Check if first column has zero
        for (int r = 0; r < rows; r++) {
            if (matrix[r][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // Use first row and column to mark zeros
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0; // mark row
                    matrix[0][c] = 0; // mark column
                }
            }
        }

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

        // Zero columns based on marks
        for (int c = 1; c < cols; c++) {
            if (matrix[0][c] == 0) {
                for (int r = 1; r < rows; r++) {
                    matrix[r][c] = 0;
                }
            }
        }

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

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

    static void PrintMatrix(int[][] matrix) {
        for (int r = 0; r < matrix.Length; r++) {
            for (int c = 0; c < matrix[0].Length; c++) {
                Console.Write(matrix[r][c]);
                if (c < matrix[0].Length - 1) Console.Write(" ");
            }
            Console.WriteLine();
        }
    }

    static void Main() {
        int[][] matrix = new int[][] {
            new int[] {1, 2, 3},
            new int[] {4, 0, 6},
            new int[] {7, 8, 9}
        };

        Solution sol = new Solution();
        sol.SetZeroes(matrix);
        PrintMatrix(matrix);
    }
}

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

Check if first row contains zero to mark later zeroing

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

Check if first column contains zero to mark later zeroing

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; } } }

Mark rows and columns to be zeroed using first row and column

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

Zero entire row if marked

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

Zero entire column if marked

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

Zero first row if originally contained zero

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

Zero first column if originally contained zero

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 cell is processed a constant number of times

Space: O(1) because we use the first row and column of the matrix itself to store markers instead of extra memory

vs Alternative: Naive approach uses extra arrays of size m and n to track rows and columns to zero, increasing space to O(m+n)

Edge Cases

Matrix with no zeros

Matrix remains unchanged

DSA C#

if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; }

Matrix with zeros only in first row and first column

First row and/or column are zeroed correctly at the end

DSA C#

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

Matrix with single element zero

Single element matrix becomes zero

DSA C#

if (matrix[0][c] == 0) { firstRowZero = true; }

When to Use This Pattern

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

Common Mistakes

Mistake: Using extra arrays for rows and columns, increasing space complexity
Fix: Use first row and first column of the matrix itself as markers to reduce space to O(1)

Mistake: Zeroing rows and columns immediately when a zero is found, corrupting markers
Fix: First mark rows and columns, then zero them in a separate pass

Mistake: Not handling the first row and first column zeroing separately
Fix: Use boolean flags to remember if first row or column originally had zeros and zero them at the end

Summary

Sets entire row and column to zero for each zero element in the matrix in place.

Use when you want to modify the matrix without extra memory to track zero 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. Replace all zeroes with ones in the matrix.

B. Count the number of zeroes 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 set entire rows and columns to zero if any element in them is zero, modifying the matrix directly without extra space.

2. Step 2: Differentiate from other operations

   Counting zeroes, replacing zeroes with ones, or sorting rows do not meet the problem's goal.

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:

   Goal is to set rows and columns zero in place = A [OK]

Hint: Focus on zero elements affecting rows and columns without extra space [OK]

Common Mistakes:

• Thinking the problem is about counting zeroes
• Trying to use extra memory like new arrays
• Confusing zero replacement with sorting

2. Which of the following C# code snippets correctly declares a 2D integer matrix named matrix with 3 rows and 3 columns?

easy

A. int[,] matrix = new int[3,3];

B. int[][] matrix = new int[3][3];

C. int matrix[3,3];

D. int[] matrix = new int[3,3];

Solution

1. Step 1: Recall C# 2D array syntax

   In C#, a rectangular 2D array is declared as int[,] matrix = new int[3,3];.

2. Step 2: Identify incorrect syntax

   int[][] matrix = new int[3][3]; uses jagged array syntax incorrectly, C is invalid in C#, and D has type mismatch.

3. Final Answer:

   int[,] matrix = new int[3,3]; -> Option A

4. Quick Check:

   Correct 2D array declaration = A [OK]

Hint: Use int[,] for 2D arrays, not jagged or invalid syntax [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Missing array type in declaration
• Using C/C++ style array declaration

3. What will be the state of the matrix after running the following C# code?

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

// Set matrix zeroes in place
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);

bool firstRowZero = false;
bool firstColZero = false;

// Check first row
for (int j = 0; j < cols; j++) {
    if (matrix[0, j] == 0) firstRowZero = true;
}
// Check first column
for (int i = 0; i < rows; i++) {
    if (matrix[i, 0] == 0) firstColZero = true;
}

// 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;
        }
    }
}

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

// Set first row zero if needed
if (firstRowZero) {
    for (int j = 0; j < cols; j++) matrix[0, j] = 0;
}
// Set first column zero if needed
if (firstColZero) {
    for (int i = 0; i < rows; i++) matrix[i, 0] = 0;
}

medium

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

B. [[1, 0, 3], [0, 0, 0], [7, 0, 9]]

C. [[1, 0, 3], [0, 0, 0], [7, 0, 0]]

D. [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Solution

1. Step 1: Identify zero positions and mark rows and columns

   Zero found at matrix[1,1]. Mark matrix[1,0] and matrix[0,1] as zero.

2. Step 2: Set zeroes based on markers

   Set matrix[1,j] and matrix[i,1] to zero for i,j > 0. First row and column have no zero, so no change there.

3. Final Answer:

   [[1, 0, 3], [0, 0, 0], [7, 0, 9]] -> Option B

4. Quick Check:

   Zero at (1,1) sets row 1 and col 1 zero = A [OK]

Hint: Mark zero rows and columns using first row/column as flags [OK]

Common Mistakes:

• Not marking first row and column correctly
• Setting zeroes before marking all zero positions
• Overwriting first row/column too early

4. The following code attempts to set matrix zeroes in place but has a bug. What is the bug?

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

int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);

bool firstRowZero = false;
bool firstColZero = false;

// Check first row
for (int j = 0; j < cols; j++) {
    if (matrix[0, j] == 0) firstRowZero = true;
}
// Check first column
for (int i = 0; i < rows; i++) {
    if (matrix[i, 0] == 0) firstColZero = true;
}

// 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;
        }
    }
}

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

// Set first row zero if needed
if (firstRowZero) {
    for (int j = 0; j < cols; j++) matrix[0, j] = 0;
}
// Set first column zero if needed
if (firstColZero) {
    for (int i = 0; i < rows; i++) matrix[i, 0] = 0;
}

medium

A. The first row zero check is done after modifying the matrix, causing incorrect results.

B. The first column zero check is missing.

C. The code does not mark zeroes in the first row and column correctly.

D. The code does not handle the case when the first element matrix[0,0] is zero.

Solution

1. Step 1: Understand the role of matrix[0,0]

   matrix[0,0] is used to mark both first row and first column zero status, but here separate booleans are used.

2. Step 2: Identify missing handling of matrix[0,0]

   If matrix[0,0] is zero, it affects both first row and column, but code only uses booleans, so it may miss this case.

3. Final Answer:

   The code does not handle the case when the first element matrix[0,0] is zero. -> Option D

4. Quick Check:

   matrix[0,0] zero affects both row and column flags = C [OK]

Hint: Remember matrix[0,0] marks both first row and column zero [OK]

Common Mistakes:

• Ignoring matrix[0,0] special role
• Checking first row/column after modifying matrix
• Not using separate flags for first row and column

5. Given a matrix:

int[,] matrix = {
  {0, 1, 2, 0},
  {3, 4, 5, 2},
  {1, 3, 1, 5}
};

Apply the Set Matrix Zeroes In Place algorithm. What is the final matrix state?

hard

A. [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

B. [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]

C. [[0, 0, 0, 0], [3, 0, 0, 0], [1, 0, 0, 0]]

D. [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Solution

1. Step 1: Identify zeroes and mark rows and columns

   Zeroes at matrix[0,0] and matrix[0,3]. Mark first row and columns 0 and 3.

2. Step 2: Set zeroes based on markers

   Set entire first row zero. Set columns 0 and 3 zero in all rows.

3. Final Answer:

   [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]] -> Option A

4. Quick Check:

   Zeroes in first row set cols 0 and 3 zero = B [OK]

Hint: Zero in first row sets entire row and columns zero [OK]

Common Mistakes:

• Not zeroing columns 0 and 3 in all rows
• Leaving first row partially unchanged
• Confusing zeroing rows vs columns