Set Matrix Zeroes

Given an m x n matrix, if any cell is 0, set its entire row and column to 0. Do it in-place with O(1) extra space.

Function signature

func SetZeroes(matrix [][]int)

Inputs / outputs

• matrix: matrix to modify in-place.
• Return: nothing; modify matrix.

Example

matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
After:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Constraints

• 0 <= m, n <= 1000

Core idea (near-solution)

Use the first row and first column as marker storage:

• If matrix[i][j] is zero, mark matrix[i][0] = 0 and matrix[0][j] = 0.
• Use two extra flags to remember whether the first row and first column themselves should be zeroed.

Invariant: after the marking pass, markers correctly identify which rows/cols need zeroing.

Algorithm (step-by-step)

1. Scan first row and first column to set row0Zero and col0Zero flags.
2. For each cell (i,j) starting from (1,1):
   • If matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
3. For each cell (i,j) starting from (1,1):
   • If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.
4. If row0Zero, zero the first row; if col0Zero, zero the first column.

Correctness sketch

• Invariant: after the marking pass, markers correctly identify which rows/cols need zeroing.
• Boundary/marker invariants ensure each cell is processed correctly.
• In-place encodings preserve original state until updates are finalized.
• Thus the final matrix matches the required transformation.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
After:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Walk:
- zero at (1,1) => mark row 1 and col 1
- zero row 1 -> [0,0,0] in middle
- zero col 1 -> final [[1,0,1],[0,0,0],[1,0,1]]

Pitfalls to avoid

• Overwriting markers too early.
• Forgetting to handle the first row/column separately.

Complexity

• Time: O(m*n)
• Extra space: O(1)

Implementation notes (Go)

• Use the first row/col as markers and track separate flags.
• Zero the first row/col at the end based on flags.