# Set Matrix Zeroes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/set-matrix-zeroes)
Canonical: https://scaleengineer.com/dsa/problems/set-matrix-zeroes
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Juspay](https://scaleengineer.com/companies/juspay), [Autodesk](https://scaleengineer.com/companies/autodesk), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
Given an `m x n` integer matrix `matrix`, if an element is `0`, set its entire row and column to `0`'s.

You must do it [in place](https://en.wikipedia.org/wiki/In-place%5Falgorithm).

**Example 1:**

![](https://assets.glich.co/dsa/set-matrix-zeroes/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/set-matrix-zeroes/image1.jpg) 

**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]]

**Constraints:**

* `m == matrix.length`
* `n == matrix[0].length`
* `1 <= m, n <= 200`
* `-231 <= matrix[i][j] <= 231 - 1`

**Follow up:**

* A straightforward solution using `O(mn)` space is probably a bad idea.
* A simple improvement uses `O(m + n)` space, but still not the best solution.
* Could you devise a constant space solution?

# Approaches
## Brute Force using an Additional Matrix
The most straightforward approach is to use an auxiliary matrix of the same dimensions as the original. We can iterate through the original matrix to find the locations of all the zeros. Then, based on these locations, we modify the auxiliary matrix by setting the corresponding rows and columns to zero. Finally, we copy the contents of the auxiliary matrix back to the original one. This approach is simple to conceptualize but highly inefficient in terms of space.
**Time:** O((m*n) * (m+n)) · **Space:** O(m*n)
**Pros:** Very simple and easy to understand.; Separates the logic of finding zeros from modifying the matrix, avoiding common pitfalls.
**Cons:** Extremely high space complexity, making it impractical for large matrices.; Inefficient time complexity, especially for matrices with many zeros.
### Explanation
This method avoids the problem of modifying the matrix while iterating over it, which could lead to a chain reaction of zeroing out unintended rows and columns. By using a separate copy, we can safely record all the required changes before applying them.

Here's the breakdown:
1.  Create a new matrix, let's call it `ans`, with the same dimensions `m x n` and copy all elements from the original `matrix` into it.
2.  Iterate through the original `matrix` using nested loops for row `i` and column `j`.
3.  If you find an element `matrix[i][j]` that is `0`, you then perform two more loops to set the entire `i`-th row and `j`-th column of the `ans` matrix to `0`.
4.  After the initial iteration over the original matrix is complete, the `ans` matrix holds the desired final state. The last step is to copy the `ans` matrix back into the original `matrix` to satisfy the in-place requirement.

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

        // Create a copy of the original matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = matrix[i][j];
            }
        }

        // Iterate through the original matrix to find zeros
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    // Set the entire row in the 'ans' matrix to 0
                    for (int k = 0; k < n; k++) {
                        ans[i][k] = 0;
                    }
                    // Set the entire column in the 'ans' matrix to 0
                    for (int k = 0; k < m; k++) {
                        ans[k][j] = 0;
                    }
                }
            }
        }

        // Copy the 'ans' matrix back to the original matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = ans[i][j];
            }
        }
    }
}
```
### Algorithm
*   Create a new matrix `ans` of size `m x n` and copy the original `matrix` into it.
*   Iterate through the original `matrix` from `(i, j) = (0, 0)` to `(m-1, n-1)`.
*   If `matrix[i][j]` is `0`:
    *   Set all elements in row `i` of the `ans` matrix to `0`.
    *   Set all elements in column `j` of the `ans` matrix to `0`.
*   After the iteration is complete, copy the `ans` matrix back to the original `matrix`.

## Using Marker Arrays
A significant improvement over the brute-force approach is to use extra space that is proportional to the dimensions of the matrix, rather than its area. We can use two separate arrays, one to mark which rows need to be zeroed and another for the columns. This reduces the space complexity from O(m*n) to O(m+n).
**Time:** O(m*n) · **Space:** O(m+n)
**Pros:** Much better space complexity than the brute-force approach.; Efficient time complexity.; The logic is still relatively straightforward.
**Cons:** Does not meet the O(1) space complexity follow-up challenge.; Uses extra space that could be significant for very large `m` or `n`.
### Explanation
The core idea is to make two passes over the matrix. 

In the first pass, we iterate through the entire matrix to identify which rows and columns should be converted to zeros. We use a boolean array `row_zero` of size `m` and another boolean array `col_zero` of size `n`. When we encounter a zero at `matrix[i][j]`, we mark `row_zero[i] = true` and `col_zero[j] = true`. 

In the second pass, we iterate through the matrix again. For each cell `matrix[i][j]`, we check our marker arrays. If either `row_zero[i]` or `col_zero[j]` is true, it means this cell belongs to a row or column that must be zeroed, so we set `matrix[i][j] = 0`.

This two-pass approach ensures that we make decisions based on the original state of the matrix without letting our modifications interfere with the logic.

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

        // First pass: find the zeros and mark the rows and columns
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row_zero[i] = true;
                    col_zero[j] = true;
                }
            }
        }

        // Second pass: set the elements to zero based on the markers
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row_zero[i] || col_zero[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
```
### Algorithm
*   Initialize a boolean array `row_zero` of size `m` and `col_zero` of size `n` with `false`.
*   Iterate through the matrix from `(i, j) = (0, 0)` to `(m-1, n-1)`.
*   If `matrix[i][j] == 0`, set `row_zero[i] = true` and `col_zero[j] = true`.
*   Iterate through the matrix again.
*   For each cell `(i, j)`, if `row_zero[i]` or `col_zero[j]` is `true`, set `matrix[i][j] = 0`.

## In-place Modification using First Row and Column
The most optimal solution achieves constant space complexity by cleverly using the first row and first column of the matrix itself as storage for the marker information. Since the first row and column will be overwritten, their original zero-status must be stored in separate variables.
**Time:** O(m*n) · **Space:** O(1)
**Pros:** Optimal space complexity, as it modifies the matrix in-place without significant extra storage.; Maintains an efficient O(m*n) time complexity.
**Cons:** The logic is more complex and less intuitive than other approaches.; It's easy to make mistakes with the order of operations, which can lead to incorrect results by erasing markers prematurely.
### Explanation
This approach avoids using any extra space proportional to the matrix size. The first row and first column are repurposed as the `row_zero` and `col_zero` marker arrays from the previous approach.

There's a catch: what if the first row or column itself needs to be zeroed? Using `matrix[0][0]` as a marker for both the first row and first column is ambiguous. To solve this, we use `matrix[0][0]` to mark the first row and a separate boolean variable, say `is_col0_zero`, to track the status of the first column.

The algorithm proceeds in these steps:
1.  First, check if the first column contains any zeros. If it does, set `is_col0_zero = true`.
2.  Next, iterate through the rest of the matrix (from the second column onwards). Use the first row and first column as markers. If `matrix[i][j] == 0`, set `matrix[i][0] = 0` and `matrix[0][j] = 0`.
3.  After marking, iterate through the matrix again (from `matrix[1][1]`) and update the values. If `matrix[i][0] == 0` or `matrix[0][j] == 0`, set `matrix[i][j] = 0`.
4.  Now, handle the first row. If `matrix[0][0] == 0`, it means the first row needs to be zeroed out.
5.  Finally, handle the first column. If `is_col0_zero` is true, zero out the first column.

The order of these steps is crucial to avoid erasing marker information before it has been used.

```java
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean isCol0Zero = false;

        // Step 1: Check if the first column needs to be zeroed
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                isCol0Zero = true;
                break;
            }
        }

        // Step 2: Use first row and col as markers for the rest of the matrix
        // Note: We check matrix[0][0] in the inner loop for the first row
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Step 3: Zero out cells based on markers in first row and col
        // We iterate from the second row/col to not corrupt markers yet
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 4: Zero out the first row if needed
        if (matrix[0][0] == 0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Step 5: Zero out the first column if needed
        if (isCol0Zero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
```
### Algorithm
*   Create a boolean variable `is_col0_zero` and check if any element in the first column is `0`. If so, set it to `true`.
*   Iterate through the matrix from `i=0` to `m-1` and `j=1` to `n-1`. If `matrix[i][j] == 0`, set `matrix[i][0] = 0` and `matrix[0][j] = 0`.
*   Iterate through the matrix from `i=1` to `m-1` and `j=1` to `n-1`. If `matrix[i][0] == 0` or `matrix[0][j] == 0`, set `matrix[i][j] = 0`.
*   Check if `matrix[0][0]` is `0`. If it is, set the entire first row to `0`.
*   Check if `is_col0_zero` is `true`. If it is, set the entire first column to `0`.

# Solutions
### CSharp

```csharp
public class Solution {
    public void SetZeroes(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        bool i0 = matrix[0].Contains(0), j0 = false;
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) {
                j0 = true;
                break;
            }
        }
        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;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (i0) {
            for (int j = 0; j < n; ++j) {
                matrix[0][j] = 0;
            }
        }
        if (j0) {
            for (int i = 0; i < m; ++i) {
                matrix[i][0] = 0;
            }
        }
    }
}
```

### Java

```java
class Solution {
public
  void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean i0 = false, j0 = false;
    for (int j = 0; j < n; ++j) {
      if (matrix[0][j] == 0) {
        i0 = true;
        break;
      }
    }
    for (int i = 0; i < m; ++i) {
      if (matrix[i][0] == 0) {
        j0 = true;
        break;
      }
    }
    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;
        }
      }
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }
    if (i0) {
      for (int j = 0; j < n; ++j) {
        matrix[0][j] = 0;
      }
    }
    if (j0) {
      for (int i = 0; i < m; ++i) {
        matrix[i][0] = 0;
      }
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var setZeroes =
  function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let i0 = matrix[0].some((v) => v == 0);
    let j0 = false;
    for (let i = 0; i < m; ++i) {
      if (matrix[i][0] == 0) {
        j0 = true;
        break;
      }
    }
    for (let i = 1; i < m; ++i) {
      for (let j = 1; j < n; ++j) {
        if (matrix[i][j] == 0) {
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }
      }
    }
    for (let i = 1; i < m; ++i) {
      for (let j = 1; j < n; ++j) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }
    if (i0) {
      for (let j = 0; j < n; ++j) {
        matrix[0][j] = 0;
      }
    }
    if (j0) {
      for (let i = 0; i < m; ++i) {
        matrix[i][0] = 0;
      }
    }
  };

```

### CPP

```cpp
class Solution {
public:
  void setZeroes(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool i0 = false, j0 = false;
    for (int j = 0; j < n; ++j) {
      if (matrix[0][j] == 0) {
        i0 = true;
        break;
      }
    }
    for (int i = 0; i < m; ++i) {
      if (matrix[i][0] == 0) {
        j0 = true;
        break;
      }
    }
    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;
        }
      }
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }
    if (i0) {
      for (int j = 0; j < n; ++j) {
        matrix[0][j] = 0;
      }
    }
    if (j0) {
      for (int i = 0; i < m; ++i) {
        matrix[i][0] = 0;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) i0 = any(v == 0 for v in matrix[0]) j0 = any(matrix[i][0] == 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if i0: for j in range(n): matrix[0][j] = 0 if j0: for i in range(m): matrix[i][0] = 0

```