Set Matrix Zeroes In Place in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the "Set Matrix Zeroes In Place" problem ask you to do?

It asks to modify a given matrix so that if an element is 0, its entire row and column are set to 0, without using extra space for another matrix.

beginner

Why is it important to do the "Set Matrix Zeroes" operation in place?

Doing it in place saves memory by not using extra space for another matrix, which is important for large data and efficient algorithms.

intermediate

What common trick is used to mark rows and columns to be zeroed without extra space?

Use the first row and first column of the matrix itself as markers to remember which rows and columns should be zeroed later.

intermediate

In the in-place solution, why do we need to separately track if the first row or first column should be zeroed?

Because the first row and column are used as markers, we need extra flags to remember if they originally contained zero to avoid losing that information.

beginner

What is the time complexity of the in-place "Set Matrix Zeroes" solution?

The time complexity is O(m*n), where m is the number of rows and n is the number of columns, because we scan the matrix multiple times but each scan is linear in size.

What is the main goal of the "Set Matrix Zeroes In Place" problem?

A Set entire rows and columns to zero if any element is zero

B Sort the matrix rows in ascending order

C Find the maximum element in the matrix

D Transpose the matrix

The problem requires setting entire rows and columns to zero if any element in them is zero.

Which part of the matrix is commonly used as markers in the in-place solution?

A Middle row and column

B Last row and last column

C First row and first column

D Diagonal elements

The first row and first column are used to mark which rows and columns should be zeroed.

Why do we need extra flags for the first row and first column in the in-place solution?

A To remember if they originally contained zero

B To speed up the algorithm

C To store the matrix size

D To avoid sorting

Because the first row and column are used as markers, we need flags to remember if they originally had zeros.

What is the space complexity of the in-place solution?

A O(m+n)

B O(m*n)

C O(log(m*n))

D O(1)

The in-place solution uses constant extra space, O(1), by using the matrix itself as markers.

What is the time complexity of the in-place "Set Matrix Zeroes" solution?

A O(m+n)

B O(m*n)

C O(m^2*n^2)

D O(log(m*n))

The solution scans the matrix multiple times but each scan is O(m*n), so total time complexity is O(m*n).

Explain how to use the first row and first column as markers to set matrix zeroes in place.

Think about how to remember which rows and columns to zero without extra space.

Describe the steps to solve the "Set Matrix Zeroes In Place" problem with O(1) extra space.

Focus on scanning the matrix multiple times and using flags.

Practice

1. What is the main goal of the Set Matrix Zeroes In Place problem?

easy

A. Replace all zeroes with ones in the matrix.

B. Count the number of zeroes 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. Sort each row of the matrix in ascending order.

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 operations

   Counting zeroes, replacing zeroes with ones, or sorting rows do not meet the problem's goal.

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 is to set rows and columns zero in place = A [OK]

Hint: Focus on zero elements affecting rows and columns without extra space [OK]

Common Mistakes:

• Thinking the problem is about counting zeroes
• Trying to use extra memory like new arrays
• Confusing zero replacement with sorting

2. Which of the following C# code snippets correctly declares a 2D integer matrix named matrix with 3 rows and 3 columns?

easy

A. int[,] matrix = new int[3,3];

B. int[][] matrix = new int[3][3];

C. int matrix[3,3];

D. int[] matrix = new int[3,3];

Solution

1. Step 1: Recall C# 2D array syntax

   In C#, a rectangular 2D array is declared as int[,] matrix = new int[3,3];.

2. Step 2: Identify incorrect syntax

   int[][] matrix = new int[3][3]; uses jagged array syntax incorrectly, C is invalid in C#, and D has type mismatch.

3. Final Answer:

   int[,] matrix = new int[3,3]; -> Option A

4. Quick Check:

   Correct 2D array declaration = A [OK]

Hint: Use int[,] for 2D arrays, not jagged or invalid syntax [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Missing array type in declaration
• Using C/C++ style array declaration

3. What will be the state of the matrix after running the following C# code?

int[,] matrix = {
  {1, 2, 3},
  {4, 0, 6},
  {7, 8, 9}
};

// Set matrix zeroes in place
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);

bool firstRowZero = false;
bool firstColZero = false;

// Check first row
for (int j = 0; j < cols; j++) {
    if (matrix[0, j] == 0) firstRowZero = true;
}
// Check first column
for (int i = 0; i < rows; i++) {
    if (matrix[i, 0] == 0) firstColZero = true;
}

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

// Set zeroes based on markers
for (int i = 1; i < rows; i++) {
    for (int j = 1; j < cols; j++) {
        if (matrix[i, 0] == 0 || matrix[0, j] == 0) {
            matrix[i, j] = 0;
        }
    }
}

// Set first row zero if needed
if (firstRowZero) {
    for (int j = 0; j < cols; j++) matrix[0, j] = 0;
}
// Set first column zero if needed
if (firstColZero) {
    for (int i = 0; i < rows; i++) matrix[i, 0] = 0;
}

medium

A. [[1, 2, 3], [4, 0, 6], [7, 8, 9]]

B. [[1, 0, 3], [0, 0, 0], [7, 0, 9]]

C. [[1, 0, 3], [0, 0, 0], [7, 0, 0]]

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

Solution

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

   Zero found at matrix[1,1]. Mark matrix[1,0] and matrix[0,1] as zero.

2. Step 2: Set zeroes based on markers

   Set matrix[1,j] and matrix[i,1] to zero for i,j > 0. First row and column have no zero, so no change there.

3. Final Answer:

   [[1, 0, 3], [0, 0, 0], [7, 0, 9]] -> Option B

4. Quick Check:

   Zero at (1,1) sets row 1 and col 1 zero = A [OK]

Hint: Mark zero rows and columns using first row/column as flags [OK]

Common Mistakes:

• Not marking first row and column correctly
• Setting zeroes before marking all zero positions
• Overwriting first row/column too early

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

int[,] matrix = {
  {1, 0, 3},
  {4, 5, 6},
  {7, 8, 9}
};

int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);

bool firstRowZero = false;
bool firstColZero = false;

// Check first row
for (int j = 0; j < cols; j++) {
    if (matrix[0, j] == 0) firstRowZero = true;
}
// Check first column
for (int i = 0; i < rows; i++) {
    if (matrix[i, 0] == 0) firstColZero = true;
}

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

// Set zeroes based on markers
for (int i = 1; i < rows; i++) {
    for (int j = 1; j < cols; j++) {
        if (matrix[i, 0] == 0 || matrix[0, j] == 0) {
            matrix[i, j] = 0;
        }
    }
}

// Set first row zero if needed
if (firstRowZero) {
    for (int j = 0; j < cols; j++) matrix[0, j] = 0;
}
// Set first column zero if needed
if (firstColZero) {
    for (int i = 0; i < rows; i++) matrix[i, 0] = 0;
}

medium

A. The first row zero check is done after modifying the matrix, causing incorrect results.

B. The first column zero check is missing.

C. The code does not mark zeroes in the first row and column correctly.

D. The code does not handle the case when the first element matrix[0,0] is zero.

Solution

1. Step 1: Understand the role of matrix[0,0]

   matrix[0,0] is used to mark both first row and first column zero status, but here separate booleans are used.

2. Step 2: Identify missing handling of matrix[0,0]

   If matrix[0,0] is zero, it affects both first row and column, but code only uses booleans, so it may miss this case.

3. Final Answer:

   The code does not handle the case when the first element matrix[0,0] is zero. -> Option D

4. Quick Check:

   matrix[0,0] zero affects both row and column flags = C [OK]

Hint: Remember matrix[0,0] marks both first row and column zero [OK]

Common Mistakes:

• Ignoring matrix[0,0] special role
• Checking first row/column after modifying matrix
• Not using separate flags for first row and column

5. Given a matrix:

int[,] matrix = {
  {0, 1, 2, 0},
  {3, 4, 5, 2},
  {1, 3, 1, 5}
};

Apply the Set Matrix Zeroes In Place algorithm. What is the final matrix state?

hard

A. [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

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

C. [[0, 0, 0, 0], [3, 0, 0, 0], [1, 0, 0, 0]]

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

Solution

1. Step 1: Identify zeroes and mark rows and columns

   Zeroes at matrix[0,0] and matrix[0,3]. Mark first row and columns 0 and 3.

2. Step 2: Set zeroes based on markers

   Set entire first row zero. Set columns 0 and 3 zero in all rows.

3. Final Answer:

   [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]] -> Option A

4. Quick Check:

   Zeroes in first row set cols 0 and 3 zero = B [OK]

Hint: Zero in first row sets entire row and columns zero [OK]

Common Mistakes:

• Not zeroing columns 0 and 3 in all rows
• Leaving first row partially unchanged
• Confusing zeroing rows vs columns