Understanding the Problem: Set Matrix Zeroes in C#

The popular Set Matrix Zeroes problem (frequently seen on LeetCode) requires modifying an m x n integer matrix in-place. If any element in the matrix is 0, its entire row and column must be set to 0.

Why the Initial Code Fails

In the attempted solution, two key bugs prevent the code from handling matrixes with multiple zeroes:

  • Interleaved Coordinates: Pushing row index i and column index j into a single List<int> without separation makes it difficult to distinguish between row and column indices.
  • Hardcoded Count Condition: The check if (lst.Count == 2) restricts execution exclusively to matrices containing exactly one zero element. Whenever a matrix contains multiple zeroes, lst.Count exceeds 2, causing the zeroing loop to be skipped completely.

Approach 1: Track Zero Rows and Columns (O(m + n) Space)

A simple and intuitive way to fix this is to record which rows and columns need to be zeroed using two HashSet<int> collections or boolean arrays. This avoids updating elements while scanning, preventing false positives.

public void SetZeroes(int[][] matrix) 
{
    int rows = matrix.Length;
    int cols = matrix[0].Length;

    var zeroRows = new HashSet<int>();
    var zeroCols = new HashSet<int>();

    // Step 1: Record all rows and columns that contain zeroes
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (matrix[i][j] == 0)
            {
                zeroRows.Add(i);
                zeroCols.Add(j);
            }
        }
    }

    // Step 2: Zero out the identified rows and columns
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (zeroRows.Contains(i) || zeroCols.Contains(j))
            {
                matrix[i][j] = 0;
            }
        }
    }
}

Approach 2: Optimal In-Place Solution (O(1) Auxiliary Space)

To optimize space complexity down to O(1), you can use the matrix's own first row and first column as flags to store zero locations. Use two boolean variables to keep track of whether the first row and column initially contained zeroes.

public void SetZeroesOptimal(int[][] matrix) 
{
    int rows = matrix.Length;
    int cols = matrix[0].Length;

    bool firstRowHasZero = false;
    bool firstColHasZero = false;

    // Step 1: Check if the first row has any zeroes
    for (int j = 0; j < cols; j++)
    {
        if (matrix[0][j] == 0)
        {
            firstRowHasZero = true;
            break;
        }
    }

    // Step 2: Check if the first column has any zeroes
    for (int i = 0; i < rows; i++)
    {
        if (matrix[i][0] == 0)
        {
            firstColHasZero = true;
            break;
        }
    }

    // Step 3: Use the first row and first 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;
            }
        }
    }

    // Step 4: Zero out cells based on markers in the first row and column
    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;
            }
        }
    }

    // Step 5: Update the first row if needed
    if (firstRowHasZero)
    {
        for (int j = 0; j < cols; j++)
        {
            matrix[0][j] = 0;
        }
    }

    // Step 6: Update the first column if needed
    if (firstColHasZero)
    {
        for (int i = 0; i < rows; i++)
        {
            matrix[i][0] = 0;
        }
    }
}

Complexity Analysis

  • Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Each element is visited a fixed number of times.
  • Space Complexity: O(1) extra space for the optimal solution since all state tracking occurs directly within the input matrix.