Set Matrix Zeroes In Place in DSA C# - Execution Trace

Concept Flow - Set Matrix Zeroes In Place

Start: Given matrix

↓

Scan matrix for zeros

↓

Mark rows and columns to zero

↓

Update matrix cells to zero

↓

Done: Matrix updated in place

We first scan the matrix to find zeros, mark their rows and columns, then update the matrix cells to zero in place.

Execution Sample

DSA C#

void SetZeroes(int[][] matrix) {
  int m = matrix.Length, n = matrix[0].Length;
  bool[] rows = new bool[m];
  bool[] cols = new bool[n];
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 0) { rows[i] = true; cols[j] = true; }
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (rows[i] || cols[j]) matrix[i][j] = 0;
    }
  }
}

This code marks rows and columns with zeros, then sets those rows and columns to zero in the matrix.

Execution Table

Step	Operation	Matrix State	Rows Marked	Columns Marked	Action
1	Start with matrix	[[1,1,1],[1,0,1],[1,1,1]]	[]	[]	Initial matrix
2	Check cell (0,0)	[[1,1,1],[1,0,1],[1,1,1]]	[]	[]	Value is 1, no mark
3	Check cell (0,1)	[[1,1,1],[1,0,1],[1,1,1]]	[]	[]	Value is 1, no mark
4	Check cell (0,2)	[[1,1,1],[1,0,1],[1,1,1]]	[]	[]	Value is 1, no mark
5	Check cell (1,0)	[[1,1,1],[1,0,1],[1,1,1]]	[]	[]	Value is 1, no mark
6	Check cell (1,1)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Value is 0, mark row 1 and col 1
7	Check cell (1,2)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Value is 1, no mark
8	Check cell (2,0)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Value is 1, no mark
9	Check cell (2,1)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Value is 1, no mark
10	Check cell (2,2)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Value is 1, no mark
11	Set zeros in marked rows and columns	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Start updating matrix
12	Update cell (0,0)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	No zero row or col, keep 1
13	Update cell (0,1)	[[1,1,1],[1,0,1],[1,1,1]]	[1]	[1]	Column 1 marked, set to 0
14	Update cell (0,2)	[[1,0,1],[1,0,1],[1,1,1]]	[1]	[1]	No zero row or col, keep 1
15	Update cell (1,0)	[[1,0,1],[1,0,1],[1,1,1]]	[1]	[1]	Row 1 marked, set to 0
16	Update cell (1,1)	[[1,0,1],[0,0,1],[1,1,1]]	[1]	[1]	Row 1 or col 1 marked, set to 0
17	Update cell (1,2)	[[1,0,1],[0,0,1],[1,1,1]]	[1]	[1]	Row 1 marked, set to 0
18	Update cell (2,0)	[[1,0,1],[0,0,0],[1,1,1]]	[1]	[1]	No zero row or col, keep 1
19	Update cell (2,1)	[[1,0,1],[0,0,0],[1,1,1]]	[1]	[1]	Column 1 marked, set to 0
20	Update cell (2,2)	[[1,0,1],[0,0,0],[1,0,1]]	[1]	[1]	No zero row or col, keep 1
21	End	[[1,0,1],[0,0,0],[1,0,1]]	[1]	[1]	Matrix updated in place

💡 All cells processed and matrix updated with zeros in marked rows and columns

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 21
rows	[]	[1]	[1]	[1]
cols	[]	[1]	[1]	[1]
matrix	[[1,1,1],[1,0,1],[1,1,1]]	[[1,1,1],[1,0,1],[1,1,1]]	[[1,1,1],[1,0,1],[1,1,1]]	[[1,0,1],[0,0,0],[1,0,1]]

Key Moments - 3 Insights

Why do we mark rows and columns first instead of setting zeros immediately?

If we set zeros immediately, new zeros would affect other cells incorrectly. Marking first (see steps 2-10) ensures we only update after full scan.

Why do we need separate arrays for rows and columns?

Because zeros can appear anywhere, we must remember all rows and columns to zero out later (see variable_tracker rows and cols after step 6).

What happens if the matrix has no zeros?

No rows or columns are marked, so the matrix remains unchanged after update (see steps 2-10 and 11-21).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which row and column are marked?

A Row 0 and Column 0

B Row 1 and Column 1

C Row 2 and Column 2

D No rows or columns marked

💡 Hint

Check the 'Rows Marked' and 'Columns Marked' columns at step 6 in execution_table

At which step does the first cell get updated to zero?

A Step 12

B Step 15

C Step 13

D Step 16

💡 Hint

Look at 'Action' and 'Matrix State' columns in execution_table rows 12 and 13

If the matrix had zeros in row 0 and column 2, how would the 'rows' and 'cols' arrays change after scanning?

A rows = [0], cols = [2]

B rows = [1], cols = [1]

C rows = [0,1], cols = [1,2]

D rows = [], cols = []

💡 Hint

Refer to variable_tracker and execution_table steps 2-10 for how rows and cols are marked

Concept Snapshot

Set Matrix Zeroes In Place:
- Scan matrix to find zeros
- Mark rows and columns to zero
- Update matrix cells to zero in place
- Use extra arrays to track rows and columns
- Avoid immediate zeroing to prevent cascading zeros

Full Transcript

We start with a matrix and scan every cell to find zeros. When a zero is found, we mark its entire row and column for zeroing later. We use two arrays to remember which rows and columns to zero out. After scanning, we update the matrix cells: if a cell is in a marked row or column, we set it to zero. This approach avoids changing cells too early, which could cause incorrect zeroing. The matrix is updated in place without extra matrix copies.

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