Set Matrix Zeroes medium

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0. You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Steps:

1. Identify Zeroes: Iterate through the matrix. Whenever we find a 0, we need to remember the row and column index. However, simply storing these indices will lead to incorrect results if we directly start zeroing rows and columns. Why? Because setting a row to zero might introduce new zeroes which will falsely trigger zeroing of more rows/columns.

2. Mark Zeroes: Instead of directly zeroing rows and columns, we use the first row and the first column as markers. We'll use the matrix[0][j] element to indicate if the j-th column needs to be zeroed. Similarly, matrix[i][0] will indicate if the i-th row needs to be zeroed.

3. Handle First Row and Column: We need to handle the first row and column separately because they are used as markers. We'll store whether the first row and the first column need to be zeroed in separate boolean variables.

4. Zero Rows and Columns: After marking, iterate through the matrix again. If matrix[0][j] == 0, set the entire j-th column to 0. If matrix[i][0] == 0, set the entire i-th row to 0.

5. Handle First Row and Column (again): Finally, set the first row to 0 if firstRowZero is true, and the first column to 0 if firstColZero is true.

Explanation:

The key idea is using the first row and column as a space-efficient way to track which rows and columns need to be zeroed. This avoids the need for extra space to store the indices of zeroes. The separate boolean variables handle the cases where the first row or first column themselves contain zeroes.

Code:

#include <vector>

void setZeroes(std::vector<std::vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    bool firstRowZero = false;
    bool firstColZero = false;

    // Check for zeroes in the first row and column and mark them
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }


    // Mark zeroes in the first row and column
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Zero out rows and columns based on markers
    for (int i = 1; i < m; ++i) {
        if (matrix[i][0] == 0) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = 0;
            }
        }
    }
    for (int j = 1; j < n; ++j) {
        if (matrix[0][j] == 0) {
            for (int i = 0; i < m; ++i) {
                matrix[i][j] = 0;
            }
        }
    }

    // Zero out the first row and column if necessary
    if (firstRowZero) {
        for (int j = 0; j < n; ++j) {
            matrix[0][j] = 0;
        }
    }
    if (firstColZero) {
        for (int i = 0; i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
}

Complexity:

• Time Complexity: O(m*n) - We iterate through the matrix multiple times.
• Space Complexity: O(1) - We use constant extra space. The first row and column are used for marking.