> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/73.-set-matrix-zeroes.md).

# 73. Set Matrix Zeroes

\#matrix #array

## Intuition

We need to **set entire rows and columns to 0** if any element is 0, **without using extra space**. The challenge is to **avoid overwriting** original 0s too early, which would cause incorrect updates.

To solve this smartly, we can use the **first row and first column of the matrix itself as flags** to remember which rows and columns should be zeroed. But since the first row and column are used as markers, we separately track if **they themselves should be zeroed**.

## Complexity

| Space Complexity | Time Complexity  |
| ---------------- | ---------------- |
| $$\text{O}(1)$$  | $$\text{O}(nm)$$ |

## Code

```java
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;

    boolean firstRowIsZero = false, firstColumnIsZero = false;

    // Step 1: Check if first row or first column contains any 0
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColumnIsZero = true;
    }
    for (int i = 0; i < n; i++) {
        if (matrix[0][i] == 0) firstRowIsZero = true;
    }

    // Step 2: Use first row and column as markers for rows and columns to zero
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0; // mark row
                matrix[0][j] = 0; // mark column
            }
        }
    }

    // Step 3: Set matrix cells to 0 based on the markers
    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: Handle first column
    if (firstColumnIsZero) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }

    // Step 5: Handle first row
    if (firstRowIsZero) {
        for (int i = 0; i < n; i++) {
            matrix[0][i] = 0;
        }
    }
}
```