Set Matrix Zeroes In Place in DSA C++

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 lights where if one light goes off, the entire row and column of lights must also go off, but you only have a small notebook to mark which rows and columns to turn off later.

Initial matrix:
1 2 3
4 0 6
7 8 9

We mark row 1 and column 1 to be zeroed later.

Dry Run Walkthrough

Input: matrix = [[1,2,3],[4,0,6],[7,8,9]]

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

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

matrix:
1 2 3
4 0 6
7 8 9
first_row_zero = false
first_col_zero = false

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

Step 2: Traverse matrix from (1,1) to mark zeros in first row and column

matrix:
1 0 3
0 0 6
7 8 9
first_row_zero = false
first_col_zero = false

Why: Mark row 1 and column 1 because matrix[1][1] is zero

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

matrix:
1 0 3
0 0 0
7 0 9
first_row_zero = false
first_col_zero = false

Why: Zero rows and columns based on markers

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

matrix:
1 0 3
0 0 0
7 0 9
first_row_zero = false

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

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

matrix:
1 0 3
0 0 0
7 0 9
first_col_zero = false

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

Result:

Final matrix:
1 0 3
0 0 0
7 0 9

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) return;
        int cols = matrix[0].size();
        if (cols == 0) return;
        bool first_row_zero = false;
        bool first_col_zero = false;

        // Check if first row has zero
        for (int c = 0; c < cols; c++) {
            if (matrix[0][c] == 0) {
                first_row_zero = true;
                break;
            }
        }

        // Check if first column has zero
        for (int r = 0; r < rows; r++) {
            if (matrix[r][0] == 0) {
                first_col_zero = true;
                break;
            }
        }

        // Use first row and column as markers
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0; // mark row
                    matrix[0][c] = 0; // mark column
                }
            }
        }

        // Zero rows based on markers
        for (int r = 1; r < rows; r++) {
            if (matrix[r][0] == 0) {
                for (int c = 1; c < cols; c++) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Zero columns based on markers
        for (int c = 1; c < cols; c++) {
            if (matrix[0][c] == 0) {
                for (int r = 1; r < rows; r++) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Zero first row if needed
        if (first_row_zero) {
            for (int c = 0; c < cols; c++) {
                matrix[0][c] = 0;
            }
        }

        // Zero first column if needed
        if (first_col_zero) {
            for (int r = 0; r < rows; r++) {
                matrix[r][0] = 0;
            }
        }
    }
};

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 0, 6},
        {7, 8, 9}
    };

    Solution sol;
    sol.setZeroes(matrix);

    for (auto& row : matrix) {
        for (auto& val : row) {
            cout << val << " ";
        }
        cout << "\n";
    }
    return 0;
}

for (int c = 0; c < cols; c++) { if (matrix[0][c] == 0) { first_row_zero = true; break; } }

Check if first row contains zero to know if it needs zeroing later

for (int r = 0; r < rows; r++) { if (matrix[r][0] == 0) { first_col_zero = true; break; } }

Check if first column contains zero to know if it needs zeroing later

for (int r = 1; r < rows; r++) { for (int c = 1; c < cols; c++) { 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 (int r = 1; r < rows; r++) { if (matrix[r][0] == 0) { for (int c = 1; c < cols; c++) { matrix[r][c] = 0; } } }

Zero entire row if marked

for (int c = 1; c < cols; c++) { if (matrix[0][c] == 0) { for (int r = 1; r < rows; r++) { matrix[r][c] = 0; } } }

Zero entire column if marked

if (first_row_zero) { for (int c = 0; c < cols; c++) { matrix[0][c] = 0; } }

Zero first row if originally contained zero

if (first_col_zero) { for (int r = 0; r < rows; r++) { matrix[r][0] = 0; } }

Zero first column if originally contained zero

Output

1 0 3 

0 0 0 

7 0 9 

Complexity Analysis

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

Space: O(1) because we use the first row and column as markers instead of extra memory

vs Alternative: Naive approach uses extra O(m+n) space to store zero rows and columns, this approach saves space by reusing matrix itself

Edge Cases

Empty matrix

Function does nothing and returns immediately

DSA C++

int rows = matrix.size(); if (rows == 0) return;

Matrix with single element zero

Entire row and column (only one cell) set to zero correctly

DSA C++

for (int c = 0; c < cols; c++) { if (matrix[0][c] == 0) first_row_zero = true; }

Matrix with zeros in first row and first column

First row and column zeroed correctly after marking

DSA C++

if (first_row_zero) { for (int c = 0; c < cols; c++) matrix[0][c] = 0; }

When to Use This Pattern

When you need to zero rows and columns in a matrix in place without extra space, use the first row and column as markers to track zero positions.

Common Mistakes

Mistake: Zeroing rows and columns immediately when a zero is found, corrupting the matrix before finishing scanning
Fix: First mark rows and columns to zero using first row and column, then zero them in a separate pass

Mistake: Not checking if first row or first column originally had zeros, causing incorrect zeroing
Fix: Use separate flags to remember if first row or column need to be zeroed at the end

Summary

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

Use when you want to modify the 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 remember 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. 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