Set Matrix Zeros

XXX. Set Matrix Zeroes

Matrix

Space Optimization

Problem Statement:

Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

• Modify matrix in-place
• Use O(1) extra space
• Preserve non-zero elements not in zero rows/cols

Algorithm:

1. **Key Insight**:
   • Use first row/column as markers
   • Special flags for first row/column
   • Process matrix in specific order

Implementation:

public void setZeroes(int[][] matrix) {
    boolean firstRow = false;
    boolean firstCol = false;
    
    // Step 1: Mark first row/col as flags
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 0) {
                if (i == 0) firstRow = true;    // Special case for first row
                if (j == 0) firstCol = true;    // Special case for first col
                matrix[0][j] = 0;               // Mark column
                matrix[i][0] = 0;               // Mark row
            }
        }
    }
    
    // Step 2: Use markers to set zeros (skip first row/col)
    for (int i = 1; i < matrix.length; i++) 
        for (int j = 1; j < matrix[0].length; j++) 
            if (matrix[0][j] == 0 || matrix[i][0] == 0) 
                matrix[i][j] = 0;
    
    // Step 3: Set first row/col at the end
    if (firstRow) setRowZero(0, matrix);
    if (firstCol) setColZero(0, matrix);
}

// Helper method to set entire row to zero
private void setRowZero(int i, int[][] matrix) {
    for (int j = 0; j < matrix[0].length; j++)
        matrix[i][j] = 0;
}

// Helper method to set entire column to zero
private void setColZero(int j, int[][] matrix) {
    for (int i = 0; i < matrix.length; i++)
        matrix[i][j] = 0;
}

Complexity:

Time Complexity: O(M × N), two passes through matrix
Space Complexity: O(1), constant extra space

Key Points:

• **Space Optimization**:
  • Use matrix itself to store zero information
  • First row/col serve as markers for rest of matrix
  • Need separate booleans for first row/col
• **Processing Order**:
  • First pass: mark zeros in first row/col
  • Second pass: set internal matrix cells
  • Final step: handle first row/col
• **Critical Details**:
  • Must handle first row/col separately
  • Process first row/col at end to avoid corruption
  • Use boolean flags to track first row/col state

Common Pitfalls:

• Processing first row/col too early
• Not handling first row/col intersection
• Corrupting markers before using them