The “Set Matrix Zeroes” problem involves modifying a given 2D matrix such that if any element in the matrix is zero, all elements in the corresponding row and column are set to zero. This is a common interview question that tests your understanding of matrix manipulation and space optimization.
Problem Statement
Given a matrix, if an element is zero, set its entire row and column to zero.
Approach
-
Identify Rows and Columns to Zero: First, you need to determine which rows and columns should be set to zero. You can do this using two sets (or boolean arrays) to track the indices of rows and columns that need to be zeroed.
-
Set Zeros: After identifying the rows and columns to be zeroed, iterate through the matrix again and set the appropriate elements to zero.
C# Implementation
Here’s a straightforward implementation of this approach in C#:
public class SetMatrixZeroes
{
public void SetZeroes(int[][] matrix)
{
int m = matrix.Length;
int n = matrix[0].Length;
bool[] rows = new bool[m];
bool[] cols = new bool[n];
// Step 1: Identify which rows and columns should be zeroed
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == 0)
{
rows[i] = true; // Mark the entire row
cols[j] = true; // Mark the entire column
}
}
}
// Step 2: Set the identified rows and columns to zero
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (rows[i] || cols[j])
{
matrix[i][j] = 0; // Set to zero if the row or column is marked
}
}
}
}
}
Explanation of the Code
-
Matrix Declaration: The method
SetZeroes
takes a jagged array (int[][] matrix
) representing the input matrix. -
Identify Rows and Columns:
- We create two boolean arrays,
rows
andcols
, to keep track of which rows and columns need to be set to zero. - We iterate through each element of the matrix. If we find a zero, we mark the corresponding row and column in our boolean arrays.
- We create two boolean arrays,
-
Set Zeros:
- In the second pass through the matrix, we check the
rows
andcols
arrays. - If a row or column is marked, we set the respective matrix element to zero.
- In the second pass through the matrix, we check the
Complexity
- Time Complexity: O(m * n), where
m
is the number of rows andn
is the number of columns. We traverse the matrix twice. - Space Complexity: O(m + n) for the boolean arrays used to track rows and columns.
Example
Given the input matrix:
1 1 1
1 0 1
1 1 1
The output will be:
1 0 1
0 0 0
1 0 1
Alternative Approach
If you want to optimize space further, you can use the first row and first column of the matrix itself to track which rows and columns should be zeroed. This approach requires careful handling of the first row and first column to avoid overwriting data during the marking phase. However, the implementation shown above is straightforward and easier to understand, especially for beginners.