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 scan the matrix to find zeros, mark which rows and columns to zero, then update the matrix in place.

Execution Sample

DSA C++

void setZeroes(vector<vector<int>>& matrix) {
  int m = matrix.size(), n = matrix[0].size();
  bool firstRowZero = false, firstColZero = false;
  // Mark zeros in first column
  for (int i = 0; i < m; i++) {
    if (matrix[i][0] == 0) firstColZero = true;
  }
  // Mark zeros in first row
  for (int j = 0; j < n; j++) {
    if (matrix[0][j] == 0) firstRowZero = true;
  }
  // Use first row and col to mark zeros
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      if (matrix[i][j] == 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }
  // Set zeros based on marks
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      if (matrix[i][0] == 0 || matrix[0][j] == 0) {
        matrix[i][j] = 0;
      }
    }
  }
  // Zero first row and col if needed
  if (firstRowZero) {
    for (int j = 0; j < n; j++) matrix[0][j] = 0;
  }
  if (firstColZero) {
    for (int i = 0; i < m; i++) matrix[i][0] = 0;
  }
}

This code sets matrix rows and columns to zero in place using first row and column as markers.

Execution Table

Step	Operation	Matrix State	Pointer/Flag Changes	Visual State
1	Check first column for zeros	[[1,2,3],[4,0,6],[7,8,9]]	firstColZero = false	1 2 3 4 0 6 7 8 9
2	Found zero at matrix[1][1], mark row 1 and col 1	[[1,0,3],[0,0,6],[7,8,9]]	matrix[1][0] = 0, matrix[0][1] = 0	1 0 3 0 0 6 7 8 9
3	Set zeros based on marks for rows and columns	[[1,0,3],[0,0,0],[7,0,9]]	matrix[1][2] set to 0 because matrix[1][0] == 0, matrix[2][1] set to 0 because matrix[0][1] == 0	1 0 3 0 0 0 7 0 9
4	Zero first row if needed (firstRowZero = false)	[[1,0,3],[0,0,0],[7,0,9]]	No change	1 0 3 0 0 0 7 0 9
5	Zero first column if needed (firstColZero = false)	[[1,0,3],[0,0,0],[7,0,9]]	No change	1 0 3 0 0 0 7 0 9
6	End	[[1,0,3],[0,0,0],[7,0,9]]	Done	1 0 3 0 0 0 7 0 9

💡 All zeros set in place; no more changes needed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
firstRowZero	false	false	false	false	false
firstColZero	false	false	false	false	false
matrix	[[1,2,3],[4,0,6],[7,8,9]]	[[1,2,3],[4,0,6],[7,8,9]]	[[1,0,3],[0,0,6],[7,8,9]]	[[1,0,3],[0,0,0],[7,0,9]]	[[1,0,3],[0,0,0],[7,0,9]]

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 saves space by marking zeros in place, as shown in execution_table step 2 where matrix[1][0] and matrix[0][1] are set to zero to mark the row and column.

Why do we check and store firstRowZero and firstColZero flags separately?

Because the first row and column are used as markers, we must separately track if they originally had zeros to zero them at the end, as seen in variable_tracker where these flags remain false and affect final zeroing.

Why do we start marking zeros from row 1 and column 1, not from 0?

Because row 0 and column 0 are used as markers, we skip them during marking to avoid overwriting marker info, as shown in execution_table steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, which cells are marked zero to indicate rows and columns to be zeroed?

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

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

C matrix[1][0] and matrix[0][1]

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

💡 Hint

Check the 'Pointer/Flag Changes' column in step 2 of execution_table.

At which step in the execution_table does the matrix cell matrix[2][1] get set to zero?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for when matrix[2][1] changes in the 'Matrix State' column.

If the first column had a zero initially, which variable would change and what would happen at the end?

A firstRowZero would be true and first row would be zeroed

B firstColZero would be true and first column would be zeroed

C Both firstRowZero and firstColZero would be false and no change

D No variables change and matrix remains same

💡 Hint

Check variable_tracker for firstColZero and final zeroing steps in execution_table.

Concept Snapshot

Set Matrix Zeroes In Place:
- Use first row and column as markers to save space.
- Scan matrix to mark zeros in first row/col.
- Update matrix cells based on markers.
- Use flags to zero first row/col if needed.
- All done in place without extra arrays.

Full Transcript

This visualization shows how to set matrix zeroes in place. We start by scanning the matrix to find zeros. Instead of extra memory, we use the first row and first column to mark which rows and columns should be zeroed. We keep two flags to remember if the first row or first column originally had zeros. Then we update the matrix cells based on these markers. Finally, if needed, we zero the first row and first column. The execution table tracks each step and matrix state, while variable tracker shows how flags and matrix change. Key moments clarify why we use markers and flags. The quiz tests understanding of marking and zeroing steps. This method efficiently updates the matrix without extra space.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the problem requirement

   The problem requires changing the matrix so that any row or column containing a zero is set entirely to zero.

2. Step 2: Note the in-place constraint

   We must do this 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 D

4. Quick Check:

   In-place zeroing = Modify matrix rows and columns [OK]

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

Common Mistakes:

• Using extra space like another matrix
• Only zeroing the element itself, not row and column
• Not handling the in-place requirement

2. Which of the following C++ code snippets correctly declares a 2D vector to represent a matrix for the Set Matrix Zeroes In Place problem?

easy

A. std::vector matrix(cols, std::vector<int>(rows));

B. std::vector<int> matrix(rows, cols);

C. std::vector matrix(rows, std::vector<int>(cols));

D. std::vector<int> matrix[rows][cols];

Solution

1. Step 1: Understand 2D vector declaration

   To create a matrix with 'rows' rows and 'cols' columns, use vector of vectors with inner vector size 'cols'.

2. Step 2: Check each option

   std::vector matrix(rows, std::vector<int>(cols)); correctly creates a vector of vectors with 'rows' outer vectors and 'cols' inner vectors each.

3. Final Answer:

   std::vector matrix(rows, std::vector<int>(cols)); -> Option C

4. Quick Check:

   Correct 2D vector syntax = std::vector matrix(rows, std::vector<int>(cols)); [OK]

Hint: Use vector of vectors with inner vector size as columns [OK]

Common Mistakes:

• Using single vector with two sizes incorrectly
• Swapping rows and columns in inner vector
• Using array syntax instead of vector

3. What will be the state of the matrix after running the following code snippet for Set Matrix Zeroes In Place?

std::vector matrix = {
  {1, 2, 3},
  {4, 0, 6},
  {7, 8, 9}
};
// Assume correct in-place zeroing function is called here
setZeroes(matrix);
// Print matrix

medium

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

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

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

D. [[1, 2, 3], [0, 0, 0], [7, 8, 9]]

Solution

1. Step 1: Identify zero positions

   The zero is at position (1,1) (second row, second column).

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

   Row 1 becomes [0,0,0], column 1 becomes zero in rows 0 and 2, so matrix becomes [[1,0,3],[0,0,0],[7,0,9]].

3. Final Answer:

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

4. Quick Check:

   Zero at (1,1) zeroes row 1 and column 1 [OK]

Hint: Zero row and column where zero found [OK]

Common Mistakes:

• Zeroing entire matrix instead of row and column
• Not zeroing column correctly
• Leaving original zero row unchanged

4. Consider this buggy code snippet for Set Matrix Zeroes In Place. What is the main error?

void setZeroes(std::vector& matrix) {
  int rows = matrix.size();
  int cols = matrix[0].size();
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (matrix[i][j] == 0) {
        for (int k = 0; k < cols; k++) matrix[i][k] = 0;
        for (int k = 0; k < rows; k++) matrix[k][j] = 0;
      }
    }
  }
}

medium

A. Modifying matrix inside loops causes multiple zeroing and incorrect results.

B. The loops do not cover all rows and columns.

C. The function does not return the modified matrix.

D. The matrix size is not checked for empty input.

Solution

1. Step 1: Analyze modification during iteration

   The code sets zeros immediately when a zero is found, changing matrix during iteration.

2. Step 2: Understand side effects

   This causes new zeros to appear and cause more zeroing, leading to incorrect results.

3. Final Answer:

   Modifying matrix inside loops causes multiple zeroing and incorrect results. -> Option A

4. Quick Check:

   Immediate modification causes cascading zeroing [OK]

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

Common Mistakes:

• Changing matrix while scanning causes wrong zeroing
• Not using markers or flags to delay zeroing
• Ignoring empty matrix edge cases

5. Given a matrix with multiple zeros, how can you efficiently set matrix zeroes in place without extra space? Choose the best approach.

hard

A. Use first row and first column as markers to store zero flags, then update matrix accordingly.

B. Create a copy of the matrix and update zeros in the copy.

C. Use a hash map to store zero positions and then update matrix.

D. Iterate multiple times over the matrix zeroing rows and columns immediately when zero found.

Solution

1. Step 1: Use first row and column as markers

   Mark zeros found in first row and column to remember which rows and columns to zero later.

2. Step 2: Update matrix based on markers

   After marking, zero out rows and columns except first row and column, then handle first row and column separately.

3. Final Answer:

   Use first row and first column as markers to store zero flags, then update matrix accordingly. -> Option A

4. Quick Check:

   In-place marking with first row/column = Use first row and first column as markers to store zero flags, then update matrix accordingly. [OK]

Hint: Use matrix edges as flags to avoid extra space [OK]

Common Mistakes:

• Using extra space violating in-place rule
• Zeroing immediately causing cascading errors
• Not handling first row and column separately