73. Set Matrix Zeroes

Intuition

When we find a zero in the matrix, we need to set its entire row and column to zeros. To achieve this in place, we can use the first row and first column of the matrix to store the zero states of the corresponding rows and columns. Additionally, we need two flags to remember if the first row and first column originally contained any zeros.

Approach

1. Initial Setup: - Initialize two flags, first_row_zero and first_col_zero, to check if the first row and the first column need to be zeroed. - Traverse the first row and the first column to update the flags.
2. Mark Rows and Columns: - Traverse the matrix starting from the second row and the second column. - If an element is zero, mark the corresponding first row and first column elements as zero.
3. Set Matrix Elements to Zero: - Traverse the matrix starting from the second row and the second column again. - If the corresponding first row or first column element is zero, set the current element to zero.
4. Zero the First Row and Column: - Use the first_row_zero and first_col_zero flags to zero out the first row and column if needed.

Complexity

Time Complexity:

O(m * n)

• We traverse the matrix multiple times, leading to a time complexity proportional to the number of elements in the matrix.

Space Complexity:

O(1)

• We use constant extra space, excluding the input matrix.

Code

C++

class Solution {
public:
    void setZeroes(vector>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector row(rows, 0);
        vector col(cols, 0);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (row[i] == 1 || col[j] == 1) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows = len(matrix)
        cols = len(matrix[0])
        row_set = set()
        col_set = set()
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 0:
                    row_set.add(i)
                    col_set.add(j)
        for i in range(rows):
            for j in range(cols):
                if i in row_set or j in col_set:
                    matrix[i][j] = 0

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[] row = new boolean[rows];
        boolean[] col = new boolean[cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

JavaScript

var setZeroes = function(matrix) {
    let row = new Array(matrix.length).fill(0)
    let col = new Array(matrix[0].length).fill(0)
    for(let i=0;i