Set matrix zeroes problem in C#

General
1

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

  1. 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.

  2. 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

  1. Matrix Declaration: The method SetZeroes takes a jagged array (int[][] matrix) representing the input matrix.

  2. Identify Rows and Columns:

    • We create two boolean arrays, rows and cols, 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.

  3. Set Zeros:

    • In the second pass through the matrix, we check the rows and cols arrays.
    • If a row or column is marked, we set the respective matrix element to zero.

Complexity

  • Time Complexity: O(m * n), where m is the number of rows and n 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.