Set Matrix Zeroes

MEDIUM✓ CHIP-TIMEDLC #73 — FULL STATEMENT ↗

The drill: Wherever a cell in a grid is 0, wipe its entire row and entire column to 0 as well — done directly on the given grid, and every original zero has to be found before any wiping starts, or a wiped cell gets mistaken for a real one.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of numbers arrives, and wherever any cell in it holds a 0, that cell's entire row and entire column must end up wiped to 0 as well.

The wiping happens on the grid that was handed in, not a fresh copy, and every original zero has to be located before any wiping starts — otherwise a cell that only became 0 because of an earlier wipe could be mistaken for one that was always 0, triggering wipes it never should have caused.

When the drill finishes, the grid holds the same dimensions it started with, just with the appropriate rows and columns flattened to zero wherever an original zero demanded it.

EX 01

matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

→ [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

SINGLE ZERO DEAD CENTER

EX 02

matrix = [[4, 5, 0], [3, 6, 7], [8, 0, 9]]

→ [[0, 0, 0], [3, 0, 0], [0, 0, 0]]

TWO ZEROS, ROWS FULLY OVERLAP

EX 03

matrix = [[0, 2, 3], [4, 5, 6], [7, 8, 9]]

→ [[0, 0, 0], [0, 5, 6], [0, 8, 9]]

ZERO AT THE TOP-LEFT CORNER

grids run up to a few hundred rows and columns
cell values are integers, positive, negative, or zero
any number of original zeroes can appear, including none
modification happens in place on the given grid

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Zeroing a row or column the moment a 0 is found risks turning a cell into a 0 that wasn't originally one — and then that fake zero would trigger its own row and column wipe. What has to happen before any wiping can safely begin?

HINT 2 THE STRUCTURE

Recording which rows and columns need wiping doesn't require a second full-size grid — a row only needs one bit of memory, and so does a column.

HINT 3 ONE STEP FROM THE ANSWER

Reuse the matrix itself: mark row 0 and column 0 as the 'needs wiping' flags for every other row and column (tracking their own original zero-ness separately), fill those flags in one pass, then wipe based on them in a second pass.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FLAG PASSPATTERN · FIRST ROW & COLUMN AS FLAGSmatrix = [[1,1,1],[1,0,1],[1,1,1]]

STEP 1

One zero, dead center at (1,1). First check: does row 0 or column 0 itself start with a zero? Neither does here.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/set-matrix-zeroes.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
        first_col_zero = any(matrix[r][0] == 0 for r in range(rows))

        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        if first_row_zero:
            for c in range(cols):
                matrix[0][c] = 0
        if first_col_zero:
            for r in range(rows):
                matrix[r][0] = 0

TIME O(ROWS·COLS)SPACE O(1) EXTRAPYTHON · RACE PACE · 23 LN

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()

        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    zero_rows.add(r)
                    zero_cols.add(c)

        for r in range(rows):
            for c in range(cols):
                if r in zero_rows or c in zero_cols:
                    matrix[r][c] = 0

TIME O(ROWS·COLS)SPACE O(ROWS+COLS)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        for (int c = 0; c < cols; c++) {
            if (matrix[0][c] == 0) firstRowZero = true;
        }
        for (int r = 0; r < rows; r++) {
            if (matrix[r][0] == 0) firstColZero = true;
        }

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

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

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

TIME O(ROWS·COLS)SPACE O(1) EXTRAJAVA · RACE PACE · 36 LN

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        Set<Integer> zeroRows = new HashSet<>();
        Set<Integer> zeroCols = new HashSet<>();

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    zeroRows.add(r);
                    zeroCols.add(c);
                }
            }
        }

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

TIME O(ROWS·COLS)SPACE O(ROWS+COLS)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED