73. Set Matrix Zeroes

The whole difficulty of Set Matrix Zeroes lives in one word from the prompt: in place. Zeroing rows and columns is trivial if you can allocate a copy — the interesting version forbids it, which forces a marking trick that’s a small classic of the matrix and geometry pattern. Get the ordering wrong and your markers erase each other.

The problem

You’re handed an m x n grid of integers. Wherever a cell holds 0, its entire row and its entire column must become 0 — and you have to mutate the grid directly, ideally without extra space that scales with its size. (Full statement on LeetCode.)

A 2x3 case makes the ripple clear:

1 2 0        0 0 0
4 5 6   →    4 5 0

The lone 0 at [0][2] wipes its row (all of row 0) and its column (all of column 2).

Intuition: mark first, sweep second — and don’t let markers erase markers

The naive read is to zero each row and column the moment you spot a 0. That corrupts the scan: the fresh zeros you just wrote look identical to the original ones, so they trigger more zeroing and the whole matrix collapses. So the real shape is two phases — first find every zero and record which rows and columns are doomed, then apply the damage in a second pass.

Where do you keep that record? A boolean array of size m for rows and one of size n for columns is the obvious $O(m + n)$ answer. The tighter move is to notice you already own two throwaway arrays inside the matrix: row 0 and column 0. Let matrix[i][0] flag “row i has a zero” and matrix[0][j] flag “column j has a zero.” That’s the $O(1)$ extra-space solution the follow-up is fishing for.

One snag: the top-left cell matrix[0][0] would have to mean two things at once — “row 0 is doomed” and “column 0 is doomed.” It can’t carry both. So the first row and first column each get one dedicated boolean outside the matrix, and you handle them last, after they’ve finished serving as marker storage for everything else.

Solution

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        // The two edges double as marker arrays, so record their own
        // zero status separately before we start scribbling on them.
        boolean firstRowHasZero = false, firstColHasZero = false;
        for (int j = 0; j < n; j++)
            if (matrix[0][j] == 0) { firstRowHasZero = true; break; }
        for (int i = 0; i < m; i++)
            if (matrix[i][0] == 0) { firstColHasZero = true; break; }

        // Phase 1 — mark. For each inner zero, stamp its row edge and
        // column edge. We never read these stamps until phase 2.
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }

        // Phase 2 — sweep. A cell dies if its row edge or column edge is marked.
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;

        // Finally the edges themselves, using the flags saved up top.
        if (firstRowHasZero)
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        if (firstColHasZero)
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

The order is load-bearing. Reading the edge flags before phase 1 is what keeps an original edge zero from being confused with a mark written during the scan. Zeroing the edges last is what keeps a premature matrix[0][j] = 0 from cascading into columns that were actually clean.

Complexity

	Time	Space
First row/column as markers	$O(m \cdot n)$	$O(1)$

Every cell is touched a constant number of times, and the only extra memory is two booleans — no array that grows with the input.

In an interview

Say the two-phase structure out loud before you touch the edges: “I’ll mark all doomed rows and columns first, then zero in a second pass, because writing zeros during the scan would feed on itself.” That single sentence is what’s being graded — it shows you caught the trap. Then introduce the first row and column as marker storage as the space optimization, and call out the matrix[0][0] collision explicitly; the two separate flags are the detail interviewers poke at. If you’re short on time, the $O(m + n)$ two-boolean-array version is a perfectly respectable stop before the $O(1)$ refinement.

This edge-as-scratch idea sits alongside the other in-place grid manipulations in the matrix and geometry pattern. If you liked reusing the array’s own structure, Rotate Image does the same trick by swapping in place, and Spiral Matrix is the companion traversal problem where boundary bookkeeping — not extra space — is the whole game.

References

• LeetCode 73 — Set Matrix Zeroes