Start learning free

LESSON 52 OF 321 · MATRIX

Set Matrix Zeroes in JavaScript: Mark First, Then Clear

Practice O(m*n) Read the full explanation

You get a grid of integers, matrix, with m rows and n columns.

Wherever a cell is 0, set its whole row and its whole column to 0. Change matrix in place and return nothing.

Only the zeros that are there at the start count. A cell you turn into 0 doesn't clear anything more.

The grid is an array of rows. Each row is an array of integers. Rows are counted from 0 at the top, columns from 0 at the left.

 

Example 1:

Input: matrix = [
  [4, 0, 6],
  [7, 8, 9]
]
Output: [
  [0, 0, 0],
  [7, 0, 9]
]
Explanation: The 0 is in row 0, column 1.
It clears row 0 and column 1.
The 7 and the 9 stay.

Example 2:

Input: matrix = [
  [2, 5, 8],
  [0, 3, 1],
  [6, 4, 0]
]
Output: [
  [0, 5, 0],
  [0, 0, 0],
  [0, 0, 0]
]
Explanation: Two cells are 0 at the start.
The 0 in row 1, column 0 clears row 1 and column 0.
The 0 in row 2, column 2 clears row 2 and column 2.
The 5 stays. Row 0 and column 1 had no 0 at the start.
The new zeros in row 0 don't count.

Example 3:

Input: matrix = [
  [7, 2, 9, 3]
]
Output: [
  [7, 2, 9, 3]
]
Explanation: There is no 0. Nothing changes.

 

Constraints:

  • 1 to 500 rows.
  • 1 to 500 columns.
  • All rows have the same length.
  • Each value fits in a 32-bit signed integer: -231 to 231 - 1.

Note:

Your algorithm should run in O(m * n) time and use O(m + n) extra space.

Follow-up: can you do it with O(1) extra space? The first row and the first column of matrix can hold the marks for the other rows and columns.

STEP 1 OF 9
    Ctrl + Enter to check

    JAVASCRIPT · MATRIX

    Set Matrix Zeroes in JavaScript, explained

    Problem overview

    The method setZeroes(matrix) receives an m x n matrix, an array of m rows with n integers each. Wherever a cell holds 0, its whole row and whole column must become 0. The change happens in place and the method returns nothing. Only the zeros present at the start count: a cell that becomes 0 during the process doesn't clear its own row and column.

    For [[1, 1, 1], [1, 0, 1], [1, 1, 1]] the only zero is at row 1, column 1, so the middle row and middle column become zeros: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]. For [[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]] the zeros clear rows 0 and 1 and columns 0 and 1, and the result is [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 11, 12]]. The 11 and 12 survive because no original zero sits in their row or column.

    Approach: remember now, clear later

    The tempting solution scans the matrix and, on finding a zero, zeroes its row and column immediately. That is wrong. The new zeros look exactly like original ones, so the scan reaches them later and clears more rows and columns than it should. On the first example, that eager version returns [[1, 0, 0], [0, 0, 0], [0, 0, 0]] instead of the expected matrix, and on the second example it turns the entire matrix into zeros.

    The fix is to split the work into two passes:

    1. Read pass: look at every cell and write down which rows and columns contain a zero. Nothing in the matrix changes yet.
    2. Write pass: set a cell to 0 whenever its row or its column was marked.

    Two boolean arrays hold the marks: zeroRow[i] says whether row i has a zero, and zeroCol[j] says the same for column j. Several zeros in the same row just mark it again, which is harmless. Both passes visit every cell once, so the time is O(m * n), and the marks use O(m + n) extra space, which is what the statement allows. The follow-up in the statement reaches O(1) extra space by keeping the marks in the matrix's own first row and first column. This lesson uses the simpler arrays.

    Step by step

    1. Store the dimensions: m is matrix.length and n is matrix[0].length. Every row has the same length, so the first row gives the column count.
    2. Create the mark arrays, zeroRow with m entries and zeroCol with n entries, all false. They are const because the arrays themselves are never replaced, only their entries change.
    3. Loop over the rows and, inside, over the columns. Together the two loops reach every cell once. This first pass only reads the matrix.
    4. Test each cell with matrix[i][j] === 0.
    5. Mark its row and column by setting zeroRow[i] and zeroCol[j] to true.
    6. Start the second pass with the same pair of nested loops. Every zero is recorded now, so changing cells can't lose information.
    7. Clear a cell when zeroRow[i] || zeroCol[j] is true by setting matrix[i][j] = 0.

    The solution in JavaScript

    class Solution {
        setZeroes(matrix) {
            const m = matrix.length;
            const n = matrix[0].length;
            const zeroRow = new Array(m).fill(false);
            const zeroCol = new Array(n).fill(false);
            for (let i = 0; i < m; i++) {
                for (let j = 0; j < n; j++) {
                    if (matrix[i][j] === 0) {
                        zeroRow[i] = true;
                        zeroCol[j] = true;
                    }
                }
            }
            for (let i = 0; i < m; i++) {
                for (let j = 0; j < n; j++) {
                    if (zeroRow[i] || zeroCol[j]) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
    

    Some JavaScript details worth knowing:

    • new Array(m).fill(false). new Array(3) alone creates an array with three empty slots, printed as [ <3 empty items> ]. Calling fill(false) gives it three real false values. The marks are then safe to read.
    • === for the zero test. It compares a number with a number and doesn't convert types. The == operator would also treat values such as "" and false as equal to 0, which can't occur in this problem but is a habit worth avoiding.
    • || short-circuits. If zeroRow[i] is already true, zeroCol[j] isn't looked at. The result is a plain boolean here because both operands are booleans.
    • In place means through the rows. Each matrix[i] is an array object, so assigning matrix[i][j] = 0 changes the caller's matrix. The method has no return, so a call gives undefined.
    • Large values are fine. JavaScript numbers are doubles, which hold every 32-bit integer exactly, including -2147483648. For [[-2147483648, 0], [7, 8]] the result is [[0, 0], [7, 0]]. The 7 survives because neither its row nor its column (column 0) holds an original zero.

    Complexity

    Time: O(m * n). Each of the two passes visits every cell once, doing constant work per cell.

    Space: O(m + n). The two boolean arrays hold one entry per row and one per column. No copy of the matrix is made.

    Edge cases and common mistakes

    • Clearing while scanning. Setting a row and column to 0 the moment a zero is seen makes the new zeros spread. For [[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]] the eager version returns all zeros, while the expected answer keeps 11 and 12.
    • No zeros. [[1, 2], [3, 4]] is returned unchanged, since no mark is ever set.
    • One row or one column. [[1, 2, 3]] has no zero and stays the same. [[1], [0], [3]] becomes [[0], [0], [0]], because the zero's column is the whole matrix.
    • A matrix holding a single 0. [[0]] stays [[0]].
    • Mixing up the dimensions. zeroRow needs m entries (rows) and zeroCol needs n (columns). Swapping them breaks on non-square matrices such as the 3 by 4 examples.
    • Returning something. The tests look at matrix itself, so a new matrix you build and return is ignored.

    Testing

    • [[1, 1, 1], [1, 0, 1], [1, 1, 1]] gives [[1, 0, 1], [0, 0, 0], [1, 0, 1]].
    • [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] gives [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]].
    • [[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]] gives [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 11, 12]].
    • [[1], [0], [3]] gives [[0], [0], [0]].
    • [[1, 2], [3, 4]] gives [[1, 2], [3, 4]].
    Keep going with JavaScript1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free