Blind 75Medium

Set Matrix Zeroes — Mark First Row and Column

Use the first row and column as markers to remember which rows and columns should be zeroed without extra space.

Matrix

View problem on LeetCode

Problem Statement

If an element is 0, set its entire row and column to 0 in-place.

Why This Problem Matters

Tests in-place matrix manipulation and careful order of operations.
Common follow-up to basic matrix traversal questions.
Highlights how to repurpose existing storage for markers.

Thought Process

First pass mark zeros

Record whether first row or first column should be zeroed separately, then use them to mark other rows/columns.

Second pass apply markers

Iterate interior of matrix; if marker in row or column is zero, set cell to zero.

Finally zero first row/column if needed

Use stored flags to handle first row/column after rest of matrix is processed.

Step-by-Step Reasoning

Check if first row or first column contains zero; store in boolean flags.
For each cell (r,c) excluding first row/column, if zero mark matrix[r][0] and matrix[0][c] as zero.
Iterate interior again; zero cells whose row or column markers are zero.
Zero first row and/or column based on stored flags.

Dry Run

Matrix [[1,1,1],[1,0,1],[1,1,1]]

Markers cause row 1 and column 1 to be zeroed.

Matrix with zero in first column

Flag ensures column zeroed after interior processing.

Complexity Analysis

Time

O(m·n)

Space

O(1)

Why

Two passes over the matrix with only constant markers.

Annotated Solution

JAVA

public class SetMatrixZeroes {
  public void setZeroes(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    boolean zeroFirstRow = false;
    boolean zeroFirstCol = false;

    for (int c = 0; c < cols; c += 1) {
      if (matrix[0][c] == 0) {
        zeroFirstRow = true;
        break;
      }
    }

    for (int r = 0; r < rows; r += 1) {
      if (matrix[r][0] == 0) {
        zeroFirstCol = true;
        break;
      }
    }

    for (int r = 1; r < rows; r += 1) {
      for (int c = 1; c < cols; c += 1) {
        if (matrix[r][c] == 0) {
          matrix[r][0] = 0;
          matrix[0][c] = 0;
        }
      }
    }

    for (int r = 1; r < rows; r += 1) {
      for (int c = 1; c < cols; c += 1) {
        if (matrix[r][0] == 0 || matrix[0][c] == 0) {
          matrix[r][c] = 0;
        }
      }
    }

    if (zeroFirstRow) {
      for (int c = 0; c < cols; c += 1) {
        matrix[0][c] = 0;
      }
    }

    if (zeroFirstCol) {
      for (int r = 0; r < rows; r += 1) {
        matrix[r][0] = 0;
      }
    }
  }
}

Reusing the first row and column as markers eliminates extra memory usage while preserving the needed information.

Common Pitfalls

Zeroing first row/column prematurely erases marker information.
Mismanaging flags leads to missing zeros when markers reside in first row/column.
Iterating interior before marking can leave stale data unprocessed.

Follow-Up Questions

How would you handle immutable matrices where in-place writes are not allowed?
Can you adapt the approach for three-dimensional matrices?

Key Takeaways

Marker reuse is a powerful in-place technique.

Processing order matters; plan passes before coding.

Edge rows/columns often need special handling in matrix problems.