A night-shift slot map is an m × n grid of bin counts. A 0 means the RFID zone failed: the whole aisle (row) and bay (column) must be treated as empty. The intern allocated boolean[] row and boolean[] col, marked infected lines, then wrote zeros. Extra O(m+n) booleans are honest. The board asked for in place — constant extra cells, same array the caller holds.

Set Matrix Zeroes asks for whole-row and whole-column infection from any 0. An array of rows already holds the cells. Extra boolean strips use that and still pay O(m+n). You may not copy into a second m × n grid. Zeroing a row on first sight of a 0 erases later zeros you still needed as column signals. Mark first, write second.

The problem

Given an m × n int[][] matrix, if any cell holds 0, set every cell in that row and that column to 0. Modify matrix itself. Other values stay unless a zero in their row or column infects them.

5 1 2          5 0 2
3 0 4    →     0 0 0
6 7 8          6 0 8

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

Note: Infection is not “set the neighbors.” A zero at (1, 1) clears row 1 and column 1. The caller’s reference must see the zeros.

Extra row and column flags are the honest brute force

One boolean per row, one per column. First pass records which lines contain a zero. Second pass writes. Correct. Extra O(m+n) space.

void setZeroesExtra(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    boolean[] row = new boolean[m];
    boolean[] col = new boolean[n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (matrix[r][c] == 0) {
                row[r] = true;
                col[c] = true;
            }
        }
    }
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (row[r] || col[c]) {
                matrix[r][c] = 0;
            }
        }
    }
}

At 3 × 3 this is a rounding error. At a few thousand rows you paid two boolean arrays for a question the matrix border can store: does this row already have a zero? does this column?

First row and first column hold the marks

The interior (r >= 1, c >= 1) stashes a row-infected bit in matrix[r][0] and a column-infected bit in matrix[0][c]. Those strips are themselves data, so two booleans remember whether the first row or the first column already contained a zero before you wrote marks. Scan the border into those booleans, mark the interior, sweep the interior, then clear column 0 / row 0 if they were originally infected. Interior first; border last.

start       after marks     after interior sweep
5 1 2       5 0 2           5 0 2
3 0 4       0 0 4           0 0 0
6 7 8       6 7 8           6 0 8

firstRowZero=false  firstColZero=false
(1,1)=0 stashed as matrix[1][0] and matrix[0][1]

1 4 0     firstRowZero=true   firstColZero=false
2 5 6     matrix[0][2] already marks column 2
after interior:  1 4 0 / 2 5 0
wipe row 0:      0 0 0 / 2 5 0

5 1       firstColZero=true   firstRowZero=false
0 4       matrix[1][0] already marks row 1
after interior:  5 1 / 0 0
wipe col 0:      0 1 / 0 0

The Java is that mark-then-sweep:

void setZeroes(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    boolean firstRowZero = false;
    boolean firstColZero = false;
    for (int c = 0; c < n; c++) {
        if (matrix[0][c] == 0) {
            firstRowZero = true;
        }
    }
    for (int r = 0; r < m; r++) {
        if (matrix[r][0] == 0) {
            firstColZero = true;
        }
    }
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                matrix[r][c] = 0;
            }
        }
    }
    if (firstColZero) {
        for (int r = 0; r < m; r++) {
            matrix[r][0] = 0;
        }
    }
    if (firstRowZero) {
        for (int c = 0; c < n; c++) {
            matrix[0][c] = 0;
        }
    }
}

Time is O(mn) — a few passes over the cells. Extra space is O(1) — two booleans, no row[] / col[]. The two-array version is the same time and easier to explain; the border version is what they want when they say “constant extra space.”

Note: Interior first; border last. Those strips are still marks. Zero-as-you-go on the first sighting of a 0 is the other trap: you destroy zeros you have not yet used as signals.

What interviewers usually poke next

  • Two extra arrays vs the border. boolean[m] and boolean[n] are legal if extra O(m+n) is allowed. Collapse them into row 0 and column 0 when they tighten the space bill.
  • matrix[0][0] as one of the flags. One boolean for the first column, top-left for the first row (or the reverse). Same idea; easier to get the last two loops backwards. Name it; do not debug it unless they ask.
  • One row or one column. The interior loops do not run. The two booleans plus the final border clears still do the work. Walk a 1 × n at the board.

You are done with this problem when you can walk the 3×3 through mark then sweep, walk a first-row zero through the two booleans, and you can say out loud why extra row[] / col[] are honest and why you must not zero a line on first sight.