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.

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