Set Matrix Zeroes In Place in DSA Rust - Build from Scratch

Set Matrix Zeroes In Place

📖 Scenario: You are working with a grid of numbers representing a warehouse inventory layout. Some spots have zero stock, and you want to mark entire rows and columns as zero if any spot in them is zero, to indicate those areas need restocking.

🎯 Goal: Modify the given 2D matrix in place so that if any element is zero, its entire row and column are set to zero.

📋 What You'll Learn

Create a 2D vector called matrix with the exact values [[1,1,1],[1,0,1],[1,1,1]]

Create two boolean variables first_row_has_zero and first_col_has_zero to track zeros in the first row and column

Implement the logic to mark rows and columns to be zeroed using the first row and column as markers

Update the matrix in place to set the marked rows and columns to zero

Print the final matrix row by row, each row as a vector

💡 Why This Matters

🌍 Real World

This technique is useful in image processing, spreadsheets, and inventory management where marking entire rows and columns based on conditions is needed.

💼 Career

Understanding in-place matrix modification is important for software engineers working with data grids, game development, and performance-critical applications.

1

Create the initial matrix

Create a 2D vector called matrix with these exact values: vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]]

DSA Rust

# Create the matrix variable with the given values
# Your code here

Hint

Use let mut matrix = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]]; to create the matrix.

2

Check first row and column for zeros

Create two boolean variables called first_row_has_zero and first_col_has_zero. Set first_row_has_zero to true if any element in the first row of matrix is zero. Set first_col_has_zero to true if any element in the first column of matrix is zero.

DSA Rust

let mut matrix = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]];
// Create boolean variables to check zeros in first row and first column
# Your code here

Hint

Use matrix[0].iter().any(|&x| x == 0) for the first row and matrix.iter().any(|row| row[0] == 0) for the first column.

3

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

Use a for loop with variable i from 1 to matrix.len() and a nested for loop with variable j from 1 to matrix[0].len(). If matrix[i][j] is zero, set matrix[i][0] and matrix[0][j] to zero.

DSA Rust

let mut matrix = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]];

let first_row_has_zero = matrix[0].iter().any(|&x| x == 0);
let first_col_has_zero = matrix.iter().any(|row| row[0] == 0);

// Mark rows and columns to be zeroed using first row and column
# Your code here

Hint

Use nested loops starting from 1 to avoid the first row and column, and mark zeros in first row and column.

4

Set zeroes in matrix and print the result

Use a for loop with variable i from 1 to matrix.len() and a nested for loop with variable j from 1 to matrix[0].len(). If matrix[i][0] or matrix[0][j] is zero, set matrix[i][j] to zero. Then, if first_row_has_zero is true, set all elements in the first row to zero. If first_col_has_zero is true, set all elements in the first column to zero. Finally, print each row of matrix using println!.

DSA Rust

let mut matrix = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]];

let first_row_has_zero = matrix[0].iter().any(|&x| x == 0);
let first_col_has_zero = matrix.iter().any(|row| row[0] == 0);

for i in 1..matrix.len() {
    for j in 1..matrix[0].len() {
        if matrix[i][j] == 0 {
            matrix[i][0] = 0;
            matrix[0][j] = 0;
        }
    }
}

// Set zeros in matrix based on markers and print the matrix
# Your code here

Hint

Use loops to update the matrix based on markers, then print each row with println!("{:?}", row);.

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