Set Matrix Zeroes In Place in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of matrix after setting zeroes in place

What is the state of the matrix after running the given code to set matrix zeroes in place?

DSA C++

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    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;
            }
        }
    }
    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;
            }
        }
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
    if (firstRowZero) {
        for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
}

// Initial matrix:
// [[1,1,1],[1,0,1],[1,1,1]]
// After calling setZeroes(matrix), what is matrix?

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

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

C [[1,0,1],[1,0,1],[1,0,1]]

D [[0,0,0],[0,0,0],[0,0,0]]

💡 Hint

Check which rows and columns contain zero and mark them first before updating the matrix.

The code first checks if the first row or first column contains zero and stores that info. Then it marks the first cell of rows and columns that contain zero. Finally, it updates the matrix cells to zero based on these marks. The first row and column are updated last if needed.

🧠 Conceptual

intermediate

Why use first row and column as markers?

In the in-place algorithm for setting matrix zeroes, why do we use the first row and first column as markers instead of extra memory?

A To avoid modifying the matrix except the first row and column.

B Because the first row and column are always zero and can be reused safely.

C To save space by not using extra arrays and keep the algorithm O(1) space.

D Because the first row and column contain the maximum values and can store markers.

💡 Hint

Think about space complexity and how to avoid extra memory.

Using the first row and column as markers allows the algorithm to remember which rows and columns to zero without extra arrays, achieving O(1) additional space.

❓ Predict Output

advanced

Output after setting zeroes for a larger matrix

What is the matrix after running the setZeroes function on the following matrix? [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

DSA C++

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    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;
            }
        }
    }
    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;
            }
        }
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
    if (firstRowZero) {
        for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
}

// Initial matrix:
// [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
// After calling setZeroes(matrix), what is matrix?

A [[0,0,0,0],[0,0,0,0],[0,0,0,0]]

B [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

C [[0,0,0,0],[3,4,5,2],[1,3,1,5]]

D [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

💡 Hint

Remember to mark rows and columns with zeroes and then update all affected cells.

The zeros at positions (0,0) and (0,3) cause the entire first row and first column and the last column to be zeroed. The rest of the matrix updates accordingly.

🔧 Debug

advanced

Identify the bug in this setZeroes variant

What error or issue will this code cause when run on a matrix with zeros? void setZeroes(vector>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector rows(m, false), cols(n, false); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { rows[i] = true; cols[j] = true; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (rows[i] || cols[j]) { matrix[i][j] = 0; } } } } // What is the main drawback of this approach compared to the in-place method?

A Uses extra space proportional to matrix size, O(m+n), not O(1).

B Fails to set zeroes correctly for the first row and column.

C Causes runtime error due to out-of-bounds access.

D Does not modify the matrix at all.

💡 Hint

Check space complexity and memory usage.

This approach uses two extra arrays to track rows and columns to zero, increasing space complexity to O(m+n) instead of O(1).

🚀 Application

expert

Minimum operations to set zeroes in place

Given a matrix of size m x n, what is the minimum number of passes over the matrix needed to set zeroes in place using the optimal algorithm?

A One pass: update zeroes as you find them

B Three passes: one to mark, one to update, one to fix first row/column

C Two passes: one to mark zeroes, one to update matrix

D Four passes: separate passes for rows, columns, update, and fix first row/column

💡 Hint

Think about how the algorithm marks zeroes and then updates the matrix.

The optimal in-place algorithm requires three passes: first to mark zeroes in the first row and column, second to update the matrix based on marks, and third to update the first row and column if needed.

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