mediumArrays & Matrix (Must-Do)

Set Matrix Zeroes

If an original matrix entry is zero, set its entire row and column to zero. Update the matrix in place; newly written zeros must not trigger additional changes.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated matrix rows, one per line.

Expected result

The updated matrix.

Case 1

Input

1 0 3
4 5 6

Expected output

0 0 0
4 0 6

Case 2

Input

1 2
3 4

Expected output

1 2
3 4

Case 3

Input

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Zeroing a whole row and column as soon as we see a 0 wipes zeros we have not scanned yet, and we cannot tell original zeros from new ones. Copying an O(mn) matrix works, but the follow-up rejects that space. m,n ≤ 200, so two scans are fine. Record which rows and columns must be zeroed, then rewrite. An m-length row mark and an n-length column mark suffice: first pass only flags, second pass writes zeros. Extra space drops from O(mn) to O(m+n), still not the constant-space follow-up.

We use arrays rows and cols to mark the rows and columns to be cleared.

Then traverse the matrix again, and clear the elements in the rows and columns marked in rows and cols.

The time complexity is O(m × n), and the space complexity is O(m+n). Where m and n are the number of rows and columns of the matrix respectively.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.