Set Matrix Zeroes In Place in DSA Rust

Mental Model

When a cell in a matrix is zero, set its entire row and column to zero without using extra space.

Analogy: Imagine a grid of light bulbs. If one bulb is off, you want to turn off all bulbs in the same row and column, but you only have a small notebook to mark which rows and columns to turn off later.

Matrix before:
1 1 1
1 0 1
1 1 1

We mark the row and column of zero cells inside the matrix itself to avoid extra space.

Dry Run Walkthrough

Input: matrix: [[1,1,1],[1,0,1],[1,1,1]]

Goal: Set entire row and column to zero for each zero cell, modifying matrix in place without extra space.

Step 1: Check first row and first column for zeros to remember if they need to be zeroed later

Matrix unchanged:
1 1 1
1 0 1
1 1 1

Why: We need to know if first row or column should be zeroed at the end because we will use them as markers

Step 2: Traverse matrix from (1,1) to mark rows and columns with zeros using first row and column

Mark row 1 and column 1 by setting matrix[1][0] and matrix[0][1] to zero:
1 0 1
0 0 1
1 1 1

Why: Marking helps us remember which rows and columns to zero without extra space

Step 3: Use marks to set zeros in rows and columns except first row and column

Set row 1 and column 1 to zero except first row and column:
1 0 1
0 0 0
1 0 1

Why: Apply zeroing based on marks to all relevant cells

Step 4: Zero first row if needed (not needed here)

Matrix unchanged:
1 0 1
0 0 0
1 0 1

Why: First row had no zero originally, so no change

Step 5: Zero first column if needed (not needed here)

Matrix unchanged:
1 0 1
0 0 0
1 0 1

Why: First column had no zero originally, so no change

Result:

Final matrix:
1 0 1
0 0 0
1 0 1

Annotated Code

DSA Rust

fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
    let rows = matrix.len();
    if rows == 0 { return; }
    let cols = matrix[0].len();

    // Check if first row has zero
    let mut first_row_zero = false;
    for c in 0..cols {
        if matrix[0][c] == 0 {
            first_row_zero = true;
            break;
        }
    }

    // Check if first column has zero
    let mut first_col_zero = false;
    for r in 0..rows {
        if matrix[r][0] == 0 {
            first_col_zero = true;
            break;
        }
    }

    // Use first row and column as markers
    for r in 1..rows {
        for c in 1..cols {
            if matrix[r][c] == 0 {
                matrix[r][0] = 0; // mark row
                matrix[0][c] = 0; // mark column
            }
        }
    }

    // Zero rows based on markers
    for r in 1..rows {
        if matrix[r][0] == 0 {
            for c in 1..cols {
                matrix[r][c] = 0;
            }
        }
    }

    // Zero columns based on markers
    for c in 1..cols {
        if matrix[0][c] == 0 {
            for r in 1..rows {
                matrix[r][c] = 0;
            }
        }
    }

    // Zero first row if needed
    if first_row_zero {
        for c in 0..cols {
            matrix[0][c] = 0;
        }
    }

    // Zero first column if needed
    if first_col_zero {
        for r in 0..rows {
            matrix[r][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.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(" "));
    }
}

for c in 0..cols { if matrix[0][c] == 0 { first_row_zero = true; break; } }

Check if first row contains zero to handle it later

for r in 0..rows { if matrix[r][0] == 0 { first_col_zero = true; break; } }

Check if first column contains zero to handle it later

for r in 1..rows { for c in 1..cols { if matrix[r][c] == 0 { matrix[r][0] = 0; matrix[0][c] = 0; } } }

Mark rows and columns to be zeroed using first row and column

for r in 1..rows { if matrix[r][0] == 0 { for c in 1..cols { matrix[r][c] = 0; } } }

Zero entire rows based on markers

for c in 1..cols { if matrix[0][c] == 0 { for r in 1..rows { matrix[r][c] = 0; } } }

Zero entire columns based on markers

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

Zero first row if it originally contained zero

if first_col_zero { for r in 0..rows { matrix[r][0] = 0; } }

Zero first column if it originally contained zero

Output

1 0 1

0 0 0

1 0 1

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each cell is visited a constant number of times

Space: O(1) because we use the matrix itself for marking instead of extra arrays

vs Alternative: Naive approach uses extra arrays of size m and n to track zeros, increasing space to O(m+n)

Edge Cases

Empty matrix

Function returns immediately without changes

DSA Rust

if rows == 0 { return; }

Matrix with no zeros

Matrix remains unchanged

DSA Rust

No markers set, so no zeroing happens

Matrix with zeros in first row and first column

First row and/or column zeroed at the end correctly

DSA Rust

if first_row_zero { ... } and if first_col_zero { ... }

When to Use This Pattern

When asked to set rows and columns to zero in a matrix in place, use the first row and column as markers to avoid extra space.

Common Mistakes

Mistake: Zeroing first row and column too early, losing marker information
Fix: Check and store if first row/column has zero before marking, then zero them at the end

Mistake: Using extra arrays for marking, increasing space complexity
Fix: Use first row and column of the matrix itself as markers

Summary

Sets entire row and column to zero for each zero cell in the matrix in place.

Use when you need to modify a matrix without extra space to mark zero rows and columns.

The key insight is to use the first row and first column as markers to track which rows and columns to zero.

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