Set Matrix Zeroes

The problem

matrix is a table of integers, given as a list of rows that all have the same length. For every cell that holds 0, the whole row and the whole column of that cell must become 0. Only the zeros of the table as given count: a cell that turns 0 under this rule does not turn its own row and column to 0. Every other cell keeps its value. Return the resulting table: you may change matrix itself or build a new one, but your function must return the result. The table may have no rows, or rows with nothing in them, and then comes back as given.

What to write

function solve(matrix: number[][]): number[][]

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

Output
[[1,0,1],[0,0,0],[1,0,1]]

Input
matrix = [[0,1],[2,3]]

Output
[[0,0],[0,3]]

Constraints

Rectangular integer matrix up to 50 × 50; empty matrices allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The matrix has at most 50 rows and 50 columns, so you can afford to go over all the cells more than once. You may also return a new matrix. Speed is not the danger here. The danger is mixing up the zeros you were given with the zeros you write yourself.

2. Hint 2: Ask a smaller question

   Take [[0, 1], [2, 3]] and work through it on paper from the top left, changing cells as you go. When you come to the second cell of the top row, it holds 0. Is that one of the zeros you were given? What would you need to have noted to be sure?

3. Hint 3: Name the pattern

   Whether a cell becomes 0 depends on one question: does its row, or its column, hold a given zero? So first collect the rows and the columns that do, without writing anything, and only then decide each cell by asking whether its row or column was collected. Collect first, then ask "is it in there?": that is hash set membership. Read the lesson on hash set membership.

4. Hint 4: State the invariant

   The two sets are filled from the given matrix only, before any cell is changed. So they hold exactly the rows and the columns that have a given zero, and a cell ends as 0 exactly when its row is in the first set or its column is in the second.

5. Hint 5: Sketch the pseudocode

   Start with two empty sets, rows and columns. For every cell at row r, column c, that holds 0: add r to rows and c to columns. Then build a new matrix: its cell at row r, column c is 0 if r is in rows or c is in columns, otherwise the old value. Return the new matrix.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

First record all rows and columns containing an original zero. Construct the result using those sets so newly written zeroes do not trigger further changes.

The slow way

Go through the cells and, each time you meet a 0, set its whole row and its whole column to 0 on the spot. That is wrong: later in the same pass you meet the zeros you wrote yourself, and they spread too. For [[0, 1], [2, 3]] the 3 is lost and every cell ends as 0.

The insight

Whether a cell must become 0 depends only on the matrix as it was given: on whether its row or its column held a 0 at the start. So look first and write later. Two sets, one for rows and one for columns, carry what the first look found over to the writing.

Step by step

1. Two sets remember which rows and which columns hold a zero. A set answers "is this row marked?" in about one step and keeps a row only once, however many zeros the row holds. Rows and columns get separate sets so that row 1 and column 1 stay apart.
2. Look at every cell of the given matrix. A zero can be anywhere, so every cell has to be seen. Nothing is written during this pass, so every zero met here is one you were given.
3. A zero marks its own row and its own column. The rule turns that whole row and that whole column to 0. Remembering the two numbers is enough to carry out the rule later, for every cell in them.
4. Build a new matrix: a cell in a marked row or column becomes 0. By now the sets are complete, so each cell can be decided by asking them. Every other cell keeps its old value, and a matrix with no cells comes out as it went in.

The same numbered steps are the comments in each solution.

function solve(matrix) {
  // 1. Two sets remember which rows and which columns hold a zero
  const rows = new Set(),
    cols = new Set();
  // 2. Look at every cell of the given matrix
  for (let r = 0; r < matrix.length; r++)
    for (let c = 0; c < matrix[r].length; c++)
      // 3. A zero marks its own row and its own column
      if (matrix[r][c] === 0) {
        rows.add(r);
        cols.add(c);
      }
  // 4. Build a new matrix: a cell in a marked row or column becomes 0
  return matrix.map((row, r) =>
    row.map((v, c) => (rows.has(r) || cols.has(c) ? 0 : v)),
  );
}

function solve(matrix: number[][]): number[][] {
  // 1. Two sets remember which rows and which columns hold a zero
  const rows = new Set(),
    cols = new Set();
  // 2. Look at every cell of the given matrix
  for (let r = 0; r < matrix.length; r++)
    for (let c = 0; c < matrix[r].length; c++)
      // 3. A zero marks its own row and its own column
      if (matrix[r][c] === 0) {
        rows.add(r);
        cols.add(c);
      }
  // 4. Build a new matrix: a cell in a marked row or column becomes 0
  return matrix.map((row, r) =>
    row.map((v, c) => (rows.has(r) || cols.has(c) ? 0 : v)),
  );
}

def solve(matrix):
    # 1. Two sets remember which rows and which columns hold a zero
    rows = set()
    cols = set()
    # 2. Look at every cell of the given matrix
    for r, row in enumerate(matrix):
        for c, value in enumerate(row):
            # 3. A zero marks its own row and its own column
            if value == 0:
                rows.add(r)
                cols.add(c)
    # 4. Build a new matrix: a cell in a marked row or column becomes 0
    return [
        [0 if r in rows or c in cols else value for c, value in enumerate(row)]
        for r, row in enumerate(matrix)
    ]

Example 2, traced

Input
matrix = [[0,1],[2,3]]

Output
[[0,0],[0,3]]

Why it works

A cell must end as 0 exactly when its row or its column holds a given zero. The first pass sees every cell before anything is written, so the sets hold exactly those rows and columns. The second pass reads only the sets and the old values, so a zero it writes can never be mistaken for a given one.

Time and space

Time O(rows × columns), extra space O(rows + columns) extra, plus output. Two passes each visit every cell once. Adding to a set or asking it takes about one step, so the time is O(rows × columns). The sets hold at most one entry per row and one per column: O(rows + columns) extra. The new matrix is the output.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not write zeros while you are still looking for them. The zeros you write are found later in the same pass and spread: the first example comes out as [[1, 0, 0], [0, 0, 0], [0, 0, 0]].
• Keep rows and columns in two separate sets. In one shared set, [[5, 5, 5, 0, 5], [1, 3, 3, 4, 4]] goes wrong: the zero in row 0 makes column 0 look marked, and the 1 becomes 0.
• Return the matrix. The tests compare what your function returns, so a function that changes matrix correctly and returns nothing fails every test, even those where the matrix has no cells.

Pattern

Hash set membership. Builds on Valid Sudoku and Rotate Image.

Keep going