73. Set Matrix Zeroes

# Question

Given an $M \times N$ integer matrix, if an element is $0$, set its entire row and column to $0$. You must perform this operation in-place using $O(1)$ extra space.

# Solution

# Pattern

In-Place State Tracking (Marker Arrays) Use the first row and first column of the input matrix itself as memory to store the states of the other rows and columns, avoiding the need for auxiliary arrays.

# How to Identify

• The problem involves a matrix or grid.
• A state change in one cell affects the entire row/column.
• There is a strict $O(1)$ space constraint (disallowing standard boolean arrays for tracking).

# Description

Step-by-step explanation:

1. State Overlap Problem: The cell matrix[0][0] belongs to both the first row and the first column. We need to decouple them. We use matrix[0][0] to track the first row, and a separate boolean variable col0 to track the first column.
2. Pass 1 (Marking): Iterate through the matrix top-down. If you encounter a 0 at matrix[i][j], you must mark its row and column. You do this by setting matrix[i][0] = 0 and matrix[0][j] = 0. If a 0 is found in the first column (j == 0), set col0 = true.
3. Pass 2 (Applying): Iterate through the matrix bottom-up, right-to-left (from m-1, n-1 down to 0, 1).
4. For each cell, check its corresponding markers at matrix[i][0] and matrix[0][j]. If either is 0, set the cell to 0.
5. Finalizing: After processing the columns 1 through N-1 for a specific row i, check the col0 boolean. If it's true, set matrix[i][0] = 0. By moving bottom-up, we ensure we don't prematurely overwrite our marker values in the first row.

# The Intuition

"Burning the ships." If you find a zero at matrix[i][j], you already know that the entire row i and column j will eventually become zeroes. Therefore, the first element of that row (matrix[i][0]) and the first element of that column (matrix[0][j]) will inevitably be overwritten to zero anyway. Since they are doomed to become zeroes, it costs us absolutely no information to overwrite them immediately and use them as flags (markers) for the rest of the algorithm.

# Complexity

# Time Complexity

We traverse the $M \times N$ matrix exactly twice (once to mark, once to apply). Operations inside the loops are $O(1)$. Thus, time scales linearly with the number of cells.

# Space Complexity

We manipulate the input matrix in-place and allocate only a single primitive boolean variable (col0) and a few loop counters. The memory footprint does not scale with $M$ or $N$.

# Code

class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean col0 = false; 
        
        // Pass 1: Mark rows and columns
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) col0 = true;
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; 
                    matrix[0][j] = 0; 
                }
            }
        }
        
        // Pass 2: Apply zeroes backward to preserve markers
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (col0) matrix[i][0] = 0;
        }
    }
}

# Caveats

• Immutability Constraints: If the system architecture enforces pure functional programming or prohibits mutating input parameters, an in-place approach is illegal. You would be forced to allocate a new matrix, making the space complexity $O(M \times N)$.
• Direction Matters: When applying the zeroes in Pass 2, you must iterate from bottom-to-top, right-to-left. Iterating top-to-bottom will immediately zero out matrix[0][0], destroying the marker for the entire first row before you process the other columns.

# Concepts to Think About

• Overlapping States: The core difficulty of this problem is that row and column zero converge at matrix[0][0]. Decoupling shared states using a single external variable is a common advanced array manipulation technique.
• Cache Locality: Matrices in Java are arrays of arrays. Accessing them row-by-row (matrix[i][j]) is highly cache-efficient because the data is loaded into the CPU L1/L2 cache sequentially. Accessing column-by-column causes cache misses.
• Time/Space Tradeoffs: A naive solution allocates an $O(M \times N)$ clone. A better solution allocates two $O(M) + O(N)$ boolean arrays. The optimal solution reuses the input. Understanding this progression is crucial for system design.

# Logical Follow-up

Question: What if the matrix is largely sparse (contains very few zeroes) but its dimensions are massive (e.g., $100,000 \times 100,000$), and we cannot modify the input matrix? Solution: Using $O(M \times N)$ space for a clone or even $O(M+N)$ space for boolean arrays might exceed memory limits or cause heavy allocations. Instead, we can use two HashSet<Integer> structures to record the distinct indices of the rows and columns that need to be zeroed. The space complexity drops to $O(Z)$, where $Z$ is the number of zeroes, which is highly efficient for sparse matrices.

Question: What if you need to perform multiple simultaneous state updates on a grid where the previous state determines the next state (e.g., Game of Life)? You cannot just overwrite the cell, because neighboring cells still need to read its original state. Solution: We use bit manipulation. We can store both the current state and the next state within the same 32-bit integer. For example, 00 (was dead, stays dead), 01 (was alive, dies), 10 (was dead, becomes alive), 11 (was alive, stays alive). This allows us to read the 1st bit for the current evaluation, and then shift bits right >> 1 at the end to apply the next state, maintaining strictly $O(1)$ space.