Set Matrix Zeroes Optimal Solution

Given a 2D matrix, your task is to modify it in-place such that if any cell in the matrix is 0, you set its entire row and column to 0.

This transformation must be done in-place, meaning you should not use extra space for a duplicate matrix. The challenge is to achieve this optimally, using constant space.

If the matrix is empty, it should remain unchanged.

Understanding the Problem

We are given a matrix of integers. The task is: If any cell in the matrix contains 0, set its entire row and column to 0.

But we must do this in-place, meaning we cannot use extra space proportional to the matrix size (no additional arrays or hash sets).

At first glance, this might seem simple—just loop through the matrix, find 0s, and mark their rows and columns. But if we directly start setting rows and columns to 0 while looping, we may unintentionally modify cells that would affect other decisions.

So, we need a smart way to remember which rows and columns need to be zeroed out, without using extra space.

Step-by-Step Solution with Example

Step 1: Analyze the Example Input

Input matrix:
[
  [1, 2, 3],
  [4, 0, 6],
  [7, 8, 9]
]

Here, there's a 0 at position (1,1). So, we should set the entire row 1 and column 1 to 0.

Step 2: Check if First Row and First Column Have Zeros

We scan the first row and first column to check if they have any 0s. We'll remember this using two boolean flags: firstRowHasZero and firstColHasZero.

Step 3: Use First Row and Column as Markers

Now, we loop through the rest of the matrix (excluding first row and column). Whenever we find a cell with 0 (like at (1,1)), we mark the entire row and column by setting matrix[i][0] = 0 and matrix[0][j] = 0.

Updated matrix after marking:
[
  [1, 0, 3],
  [0, 0, 6],
  [7, 8, 9]
]

Step 4: Use the Markers to Zero Out Matrix

We again loop through the matrix (excluding first row and column). For each cell, if either matrix[i][0] or matrix[0][j] is 0, we set matrix[i][j] = 0.

Intermediate matrix:
[
  [1, 0, 3],
  [0, 0, 0],
  [7, 0, 9]
]

Step 5: Handle the First Row and Column

If firstRowHasZero is true, set the entire first row to 0. If firstColHasZero is true, set the entire first column to 0. In our example, they are false, so no changes.

Step 6: Final Output

Final matrix:
[
  [1, 0, 3],
  [0, 0, 0],
  [7, 0, 9]
]

Edge Cases

• No zeros in matrix: No changes will happen. The matrix stays the same.
• All elements are zero: Entire matrix will remain zeros.
• Zero only in first row or column: This is why we track first row/column using separate flags, so we don’t lose important information while marking.
• Empty matrix: Just return it as is. No processing needed.

Finally

This solution is elegant because it modifies the matrix in-place using its own first row and column to mark changes. It avoids extra space usage, operates in O(m × n) time, and uses only O(1) additional space. It also handles tricky edge cases by separating the handling of first row and column.

For beginners, always focus on understanding how and why each step is done, especially when modifying data in-place.

1. Given a 2D matrix mat.
2. Use the first row and first column as markers to indicate if a row or column should be set to zero.
3. Check if the first row and first column themselves contain any zero using two separate flags.
4. Traverse the rest of the matrix:
5. → If any element is 0, mark its row and column in the first row and column.
6. Traverse the matrix again (excluding first row and column):
7. → If mat[i][0] == 0 or mat[0][j] == 0, set mat[i][j] = 0.
8. Finally, update the first row and first column based on the flags.