Set Matrix Zeroes In Place in DSA Rust - Execution Trace

Concept Flow - Set Matrix Zeroes In Place

Start

↓

Scan matrix for zeros

↓

Mark rows and columns to zero

↓

Update matrix cells to zero

↓

Done

The flow scans the matrix to find zeros, marks the rows and columns to be zeroed, then updates the matrix in place.

Execution Sample

DSA Rust

fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
    let (m, n) = (matrix.len(), matrix[0].len());
    let mut col0_zero = false;
    
    for i in 0..m {
        if matrix[i][0] == 0 {
            col0_zero = true;
        }
        for j in 1..n {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    for i in 1..m {
        for j in 1..n {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0;
            }
        }
    }

    if matrix[0][0] == 0 {
        for j in 0..n {
            matrix[0][j] = 0;
        }
    }

    if col0_zero {
        for i in 0..m {
            matrix[i][0] = 0;
        }
    }
}

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

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Initial matrix	[[1,1,1],[1,0,1],[1,1,1]]	col0_zero = false	1 1 1 1 0 1 1 1 1
2	Find zero at (1,1), mark row 1 and col 1	[[1,0,1],[0,0,1],[1,1,1]]	matrix[1][0]=0, matrix[0][1]=0	1 0 1 0 0 1 1 1 1
3	No zero in first column, col0_zero remains false	[[1,0,1],[0,0,1],[1,1,1]]	col0_zero = false	1 0 1 0 0 1 1 1 1
4	Update cells except first row/col based on markers	[[1,0,1],[0,0,0],[1,0,1]]	Set matrix[1][2]=0, matrix[2][1]=0	1 0 1 0 0 0 1 0 1
5	matrix[0][0] == 1, no zero first row update	[[1,0,1],[0,0,0],[1,0,1]]	No change	1 0 1 0 0 0 1 0 1
6	col0_zero false, no zero first column update	[[1,0,1],[0,0,0],[1,0,1]]	No change	1 0 1 0 0 0 1 0 1
7	End	[[1,0,1],[0,0,0],[1,0,1]]	Final matrix	1 0 1 0 0 0 1 0 1

💡 All cells updated based on markers, matrix zeroes set in place.

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
col0_zero	false	false	false	false
matrix[0][0]	1	1	1	1
matrix[0][1]	1	0	0	0
matrix[1][0]	1	0	0	0
matrix[1][1]	0	0	0	0
matrix[1][2]	1	1	0	0
matrix[2][1]	1	1	0	0

Key Moments - 3 Insights

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

Using the first row and column as markers saves space by not needing extra arrays. See step 2 in execution_table where matrix[1][0] and matrix[0][1] are set to zero to mark rows and columns.

Why do we check and update the first row and first column separately at the end?

Because the first row and column are used as markers, their original zero state must be tracked separately (col0_zero variable) and updated last to avoid overwriting markers prematurely. See steps 5 and 6.

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

It means the first row needs to be zeroed. The code checks matrix[0][0] and updates the first row accordingly in step 5.

Visual Quiz - 3 Questions

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

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 Changes' and 'Matrix State' columns at step 2 in execution_table.

At which step does the matrix update cells based on the markers in the first row and column?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the step where 'Update cells except first row/col based on markers' happens in execution_table.

If the first cell matrix[0][0] was zero initially, what additional update would happen?

A Both first row and first column would be zeroed

B First row would be zeroed only

C First column would be zeroed only

D No change to first row or column

💡 Hint

Refer to step 5 in execution_table and the key_moments about matrix[0][0] zero check.

Concept Snapshot

Set Matrix Zeroes In Place:
- Use first row and column as markers for zero rows/columns.
- Scan matrix to mark zeros.
- Update matrix cells based on markers.
- Handle first row and column separately.
- Achieves O(1) extra space in-place update.

Full Transcript

This visualization shows how to set matrix zeroes in place by using the first row and column as markers. Initially, the matrix is scanned to find zeros. When a zero is found, the corresponding first row and first column cells are set to zero to mark that entire row and column should be zeroed. A boolean variable tracks if the first column itself contains zero. Then, the matrix cells except the first row and column are updated to zero if their row or column is marked. Finally, the first row and first column are updated if needed based on the markers and the boolean variable. This method avoids extra memory by reusing the matrix itself for marking. The execution table traces each step with matrix states and pointer changes. Key moments clarify why the first row and column are handled separately and how markers work. The quiz tests understanding of marker placement, update steps, and special cases. This approach efficiently sets zeroes in place with clear stepwise changes.

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. Count the number of zero 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. Replace all zero elements with ones.

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 options

   Options A, B, and C do not match the problem's goal of modifying rows and columns based on zero elements.

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 = Modify matrix rows and columns in place [OK]

Hint: Focus on zero elements affecting entire rows and columns [OK]

Common Mistakes:

• Thinking only to count zeros
• Trying to use extra memory
• Confusing with sorting or replacing zeros

2. Which Rust syntax correctly declares a mutable 2D vector named matrix with 3 rows and 3 columns initialized to 1?

easy

A. let mut matrix = vec![vec![1; 3]; 3];

B. let mut matrix = vec![1; 3][3];

C. let matrix = vec![vec![1; 3]; 3];

D. let matrix = vec![1; 3][3];

Solution

1. Step 1: Identify mutable declaration

   To modify the matrix later, it must be declared mutable using let mut.

2. Step 2: Correct 2D vector initialization

   The syntax vec![vec![1; 3]; 3] creates a 3x3 vector filled with 1s. Options B and D are invalid syntax. let matrix = vec![vec![1; 3]; 3]; lacks mut.

3. Final Answer:

   let mut matrix = vec![vec![1; 3]; 3]; -> Option A

4. Quick Check:

   Mutable 2D vector with correct syntax = let mut matrix = vec![vec![1; 3]; 3]; [OK]

Hint: Use let mut and nested vec! for 2D vectors [OK]

Common Mistakes:

• Forgetting mut keyword
• Using invalid vector syntax
• Confusing 1D and 2D vector initialization

3. Given the following Rust code snippet, what will be the printed matrix after calling set_zeroes(&mut matrix)?

fn set_zeroes(matrix: &mut Vec) {
    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut row_zero = false;

    for i in 0..rows {
        if matrix[i][0] == 0 {
            row_zero = true;
        }
        for j in 1..cols {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    for i in 1..rows {
        for j in 1..cols {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0;
            }
        }
    }

    if matrix[0][0] == 0 {
        for j in 0..cols {
            matrix[0][j] = 0;
        }
    }

    if row_zero {
        for i in 0..rows {
            matrix[i][0] = 0;
        }
    }
}

fn main() {
    let mut matrix = vec![
        vec![1, 1, 1],
        vec![1, 0, 1],
        vec![1, 1, 1],
    ];
    set_zeroes(&mut matrix);
    for row in matrix {
        println!("{:?}", row);
    }
}

medium

A. [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

B. [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

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

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

Solution

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

   The zero is at position (1,1). The first loop marks row 1 and column 1 by setting matrix[1][0] and matrix[0][1] to zero.

2. Step 2: Set zeros based on marks

   The second loop sets elements to zero if their row or column is marked. This changes matrix[0][1], matrix[1][0..2], and matrix[2][1] to zero.

3. Final Answer:

   [[1, 0, 1], [0, 0, 0], [1, 0, 1]] -> Option A

4. Quick Check:

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

Hint: Mark first row and column to track zeros, then update matrix [OK]

Common Mistakes:

• Not marking first row and column correctly
• Overwriting zeros too early
• Ignoring the first column zero flag

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

fn set_zeroes(matrix: &mut Vec) {
    let rows = matrix.len();
    let cols = matrix[0].len();

    for i in 0..rows {
        for j in 0..cols {
            if matrix[i][j] == 0 {
                for k in 0..rows {
                    matrix[k][j] = 0;
                }
                for l in 0..cols {
                    matrix[i][l] = 0;
                }
            }
        }
    }
}

medium

A. It does not check for empty matrix before accessing elements.

B. It modifies the matrix while iterating, causing incorrect zero propagation.

C. It uses incorrect loop ranges causing out-of-bounds errors.

D. It uses immutable references instead of mutable ones.

Solution

1. Step 1: Analyze matrix modification during iteration

   The function sets zeros immediately when it finds a zero, which changes the matrix during iteration.

2. Step 2: Understand effect of immediate modification

   This causes new zeros to be found in later iterations, incorrectly zeroing more rows and columns than intended.

3. Final Answer:

   It modifies the matrix while iterating, causing incorrect zero propagation. -> Option B

4. Quick Check:

   Immediate zeroing during iteration causes errors [OK]

Hint: Avoid changing matrix while scanning for zeros; mark first then update [OK]

Common Mistakes:

• Changing matrix elements inside nested loops
• Not using markers to delay zeroing
• Ignoring matrix size checks

5. You have a 4x4 matrix:

[
  [1, 2, 0, 4],
  [5, 6, 7, 8],
  [9, 0, 11, 12],
  [13, 14, 15, 16]
]

Using the in-place algorithm that uses the first row and column as markers, what will be the matrix after applying set_zeroes?

hard

A. [[0, 0, 0, 0], [5, 6, 0, 8], [0, 0, 0, 0], [13, 14, 0, 16]]

B. [[1, 2, 0, 4], [5, 6, 0, 8], [0, 0, 0, 0], [13, 14, 0, 16]]

C. [[0, 2, 0, 4], [5, 6, 0, 8], [0, 0, 0, 0], [13, 14, 0, 16]]

D. [[0, 0, 0, 0], [5, 0, 0, 8], [0, 0, 0, 0], [13, 0, 0, 16]]

Solution

1. Step 1: Mark rows and columns using first row and column

   Zeros at (0,2) and (2,1) mark row 0, row 2, column 2, and column 1 as zero.

2. Step 2: Update matrix based on markers

   Set all elements in rows 0 and 2, and columns 1 and 2 to zero. Also, since matrix[0][0] is zero (due to marking), first row is zeroed. First column is zeroed only where rows are marked since no original first column zero.

3. Final Answer:

   [[0, 0, 0, 0], [5, 0, 0, 8], [0, 0, 0, 0], [13, 0, 0, 16]] -> Option D

4. Quick Check:

   First row and column mark zeros correctly [OK]

Hint: Remember to zero first row and column if marked [OK]

Common Mistakes:

• Forgetting to zero first row or column
• Not marking all affected rows and columns
• Incorrectly zeroing unrelated cells