Set Matrix Zeroes

Summary

Given a matrix, set all elements in that column or row to zero if an element is zero. The problem requires us to modify the input matrix to have zeros at certain positions based on whether other elements are zero.

Detailed Explanation

To solve this problem, we can iterate through each element of the matrix and check if it's equal to zero. If it is, then mark the column and row as ones that need to be set to zero. Then, after marking all such columns and rows, we go back and set all elements in those columns and rows to zero.

Here's a step-by-step breakdown:

1. Initialize three sets: rowsToZero, colsToZero to keep track of the rows and columns that need to be set to zero.
2. Iterate through each element of the matrix.
   • If an element is equal to zero, mark the row and column as ones that need to be set to zero by adding them to rowsToZero and colsToZero respectively.
3. Once all elements are processed, iterate through rowsToZero and set all elements in those rows to zero.
4. Then, iterate through colsToZero and set all elements in those columns to zero.

Time complexity: O(M*N), where M is the number of rows and N is the number of columns in the matrix. Space complexity: O(1), as we only use a constant amount of space to store the sets.

Optimized Solutions

Java

java
public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] rowsToZero = new boolean[m];
        boolean[] colsToZero = new boolean[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowsToZero[i] = true;
                    colsToZero[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rowsToZero[i] || colsToZero[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Python

python
def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    rowsToZero = [False]*m
    colsToZero = [False]*n

    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                rowsToZero[i] = True
                colsToZero[j] = True

    for i in range(m):
        for j in range(n):
            if rowsToZero[i] or colsToZero[j]:
                matrix[i][j] = 0

C++

cpp
void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<bool> rowsToZero(m, false);
    vector<bool> colsToZero(n, false);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                rowsToZero[i] = true;
                colsToZero[j] = true;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (rowsToZero[i] || colsToZero[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

JavaScript

javascript
function setZeroes(matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    let rowsToZero = new Array(m).fill(false);
    let colsToZero = new Array(n).fill(false);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                rowsToZero[i] = true;
                colsToZero[j] = true;
            }
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (rowsToZero[i] || colsToZero[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}