☕ DSA Java Articles

Topics › Arrays › Medium

Set Matrix Zeroes

Medium TUF ID 911 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × m integer matrix. If any cell is 0, set its entire row and entire column to 0. Do this in place. The trap is that zeros you write must not be confused with zeros that were originally there, otherwise one zero cascades and wipes the whole matrix. The follow-up asks for a solution using O(1) extra space.

Constraints: 1 ≤ n, m ≤ 200 on LeetCode (the code also handles an empty matrix), values fit in a 32-bit signed integer and may be negative.

Example 1

matrix = [[1, 1, 1],
          [1, 0, 1],
          [1, 1, 1]]
answer = [[1, 0, 1],
          [0, 0, 0],
          [1, 0, 1]]         // row 1 and column 1 become zero

Example 2

matrix = [[0, 1, 2, 0],
          [3, 4, 5, 2],
          [1, 3, 1, 5]]
answer = [[0, 0, 0, 0],
          [0, 4, 5, 0],
          [0, 3, 1, 0]]      // row 0, column 0 and column 3

Approach 1: Brute force, read from a copy

Intuition. The cascade problem disappears if we never read a zero we wrote ourselves. The simplest way to guarantee that is to keep an untouched copy of the input: scan the copy for zeros and clear rows and columns in the original. Every zero found in the copy is an original zero by construction.

A popular textbook variant marks cells with -1 instead of 0 on the first pass and converts the -1s to 0 afterwards. That only works if -1 cannot be a legitimate value; with negative inputs it corrupts data. The copy approach has no such assumption.

Algorithm.

  1. Clone every row of the matrix into original.
  2. For every cell (i, j) with original[i][j] == 0: set all of row i and all of column j in matrix to 0.
static void bruteForce(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
    int[][] original = new int[n][];
    for (int i = 0; i < n; i++) original[i] = matrix[i].clone();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (original[i][j] == 0) {
                for (int c = 0; c < m; c++) matrix[i][c] = 0;   // whole row i
                for (int r = 0; r < n; r++) matrix[r][j] = 0;   // whole column j
            }
        }
    }
}

Complexity. Time O(n·m·(n + m)): every original zero costs O(n + m) writes, and in the worst case there are n·m zeros. Space O(n·m) for the copy.

The repeated clearing is wasteful: if a row contains ten zeros we clear it ten times. All we actually need to remember is which rows and which columns contain a zero.

Approach 2: Better, row and column marker arrays

Intuition. The final value of cell (i, j) is 0 exactly when row i had a zero or column j had a zero. That is a property of the row and of the column, not of the individual cell, so two boolean arrays zeroRow[n] and zeroCol[m] capture everything we need. One pass fills the markers from the original matrix; a second pass applies them. Because the markers are collected before any write happens, written zeros can never influence the result.

Algorithm.

  1. Allocate zeroRow[n] and zeroCol[m], all false.
  2. Pass 1: for every (i, j) with matrix[i][j] == 0, set zeroRow[i] = zeroCol[j] = true.
  3. Pass 2: for every (i, j), if zeroRow[i] || zeroCol[j], set matrix[i][j] = 0.
static void better(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
    boolean[] zeroRow = new boolean[n], zeroCol = new boolean[m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                zeroRow[i] = true;
                zeroCol[j] = true;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (zeroRow[i] || zeroCol[j]) matrix[i][j] = 0;
        }
    }
}

Complexity. Time O(n·m): two full passes. Space O(n + m) for the two marker arrays.

This is the version to write first in an interview. The optimal version below is the same idea with the marker arrays squeezed into the matrix itself.

Approach 3: Optimal, use the first row and column as markers

Intuition. Where could we store n + m booleans without allocating? In the matrix. Row 0 has m cells and column 0 has n cells, so use matrix[0][j] as the marker for column j and matrix[i][0] as the marker for row i: a zero there means “this column/row must be cleared”. The two markers overlap at matrix[0][0], which we let stand for row 0 only, and we keep a single extra boolean col0 for column 0.

The subtle part is ordering. Once markers are written into row 0 and column 0, those cells no longer hold their original values, so we must (a) fill the inner cells (i ≥ 1, j ≥ 1) first, using the markers, (b) then handle row 0 using matrix[0][0], and (c) finally handle column 0 using col0. Doing row 0 or column 0 before the inner cells would destroy markers that the inner cells still need.

Algorithm.

  1. col0 = false. For each row i: if matrix[i][0] == 0 set col0 = true. For each j ≥ 1 with matrix[i][j] == 0: set matrix[i][0] = 0 and matrix[0][j] = 0.
  2. For every inner cell (i ≥ 1, j ≥ 1): if matrix[i][0] == 0 || matrix[0][j] == 0, set it to 0.
  3. If matrix[0][0] == 0, set all of row 0 to 0.
  4. If col0, set all of column 0 to 0.
static void optimal(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
    if (n == 0 || m == 0) return;
    boolean col0 = false;                        // does column 0 need to become zero?
    for (int i = 0; i < n; i++) {
        if (matrix[i][0] == 0) col0 = true;
        for (int j = 1; j < m; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;                // row marker for row i
                matrix[0][j] = 0;                // column marker for column j
            }
        }
    }
    for (int i = 1; i < n; i++) {                // inner cells: read the markers
        for (int j = 1; j < m; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        }
    }
    if (matrix[0][0] == 0) {                     // matrix[0][0] is the marker for row 0
        for (int j = 0; j < m; j++) matrix[0][j] = 0;
    }
    if (col0) {                                  // finally column 0, from the separate flag
        for (int i = 0; i < n; i++) matrix[i][0] = 0;
    }
}

Dry run on example 2, [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]:

Step State
Pass 1, row 0 matrix[0][0] == 0 so col0 = true; matrix[0][3] == 0 so row marker matrix[0][0] = 0, column marker matrix[0][3] = 0
Pass 1, rows 1 and 2 no zeros; markers unchanged
Inner cells column markers: matrix[0][1] = 1, matrix[0][2] = 2, matrix[0][3] = 0; row markers matrix[1][0] = 3, matrix[2][0] = 1. Only column 3 is cleared: matrix[1][3] = matrix[2][3] = 0
Row 0 matrix[0][0] == 0, so row 0 becomes [0, 0, 0, 0]
Column 0 col0 is true, so matrix[1][0] = matrix[2][0] = 0

Result [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]].

Complexity. Time O(n·m): two passes over the matrix plus O(n + m) for the edges. Space O(1): a single boolean.

Why does matrix[0][0] correctly stand for row 0? It is set to zero either because it was originally zero (then row 0 must indeed be cleared) or because some matrix[0][j] with j ≥ 1 was zero (again, row 0 must be cleared). Column markers are only ever written at j ≥ 1, so they never touch matrix[0][0]; that is why column 0 needs its own flag.

Edge cases and pitfalls