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 based on marks

↓

Done: Matrix updated in place

We scan the matrix to find zeros, mark their rows and columns, then update the matrix cells to zero accordingly, all done inside the original matrix.

Execution Sample

DSA C

void setZeroes(int** matrix, int rows, int cols) {
  // Use first row and column as markers
  // Mark zeros
  // Update matrix
}

This code sets entire row and column to zero if an element is zero, modifying the matrix in place.

Execution Table

Step	Operation	Nodes in Matrix	Pointer Changes	Visual State
1	Scan matrix to find zeros and mark first row/col	Matrix with initial values	Set matrix[0][2]=0 (mark col 2) and matrix[1][0]=0 (mark row 1) because matrix[1][2] == 0	[[1,2,3],[4,5,0],[7,8,9]] → [[1,2,0],[0,5,0],[7,8,9]]
2	Use marks to set zeros in matrix except first row/col	Matrix with marks in first row and col	Set matrix[1][1]=0 and matrix[2][2]=0	[[1,2,0],[0,5,0],[7,8,9]] → [[1,2,0],[0,0,0],[7,8,0]]
3	Set first row and first column zeros if needed	Check if first row or col had zero originally	No changes (row_zero_flag=false, col_zero_flag=false)	[[1,2,0],[0,0,0],[7,8,0]] → no change
4	Finish	Matrix updated in place	No pointer changes	[[1,2,0],[0,0,0],[7,8,0]] final

💡 All rows and columns with zeros updated in place, no extra space used.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
matrix	[[1,2,3],[4,5,0],[7,8,9]]	[[1,2,0],[0,5,0],[7,8,9]]	[[1,2,0],[0,0,0],[7,8,0]]	[[1,2,0],[0,0,0],[7,8,0]]	[[1,2,0],[0,0,0],[7,8,0]]
row_zero_flag	false	false	false	false	false
col_zero_flag	false	false	false	false	false

Key Moments - 3 Insights

Why do we use the first row and first column as markers instead of extra arrays?

Using the first row and column as markers saves space by not needing extra arrays. This is shown in execution_table step 1 where we mark zeros in the matrix itself.

How do we avoid overwriting the first row and column before using their markers?

We use separate flags (row_zero_flag and col_zero_flag) to remember if the first row or column originally had zeros, so we update them last. This is tracked in variable_tracker.

What happens if the first cell matrix[0][0] is zero?

It means both first row and first column need to be zeroed. We handle this by using separate flags to track first row and column zeros independently, as shown in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, which cells are marked as zero in the first row and column?

A matrix[0][2] and matrix[1][0]

B matrix[0][1] and matrix[2][0]

C matrix[1][2] and matrix[2][1]

D matrix[0][0] and matrix[1][1]

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns in step 1 of execution_table.

At which step in the execution_table do we update the matrix cells to zero based on the markers?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the step where 'Use marks to set zeros' is described.

If the first row originally had no zeros, what would be the value of row_zero_flag after step 1?

A undefined

B true

C false

D depends on matrix size

💡 Hint

Refer to variable_tracker row_zero_flag values after step 1.

Concept Snapshot

Set Matrix Zeroes In Place:
- Scan matrix to find zeros
- Use first row and column as markers
- Use flags for first row/col zeros
- Update matrix cells based on markers
- Update first row and column last
- No extra space used

Full Transcript

The Set Matrix Zeroes In Place algorithm scans the matrix to find zeros. It uses the first row and first column to mark which rows and columns should be zeroed. Separate flags track if the first row or column originally had zeros to avoid premature overwriting. After marking, the matrix is updated in place by setting cells to zero based on these markers. Finally, the first row and column are updated if needed. This approach modifies the matrix without extra space.