Set Matrix Zeroes

1. The obvious way

   Copy the matrix and write zeros into the copy: O(rows x columns) extra space.

2. The key insight

   Pass 1: for each cell equal to 0 add its row to zero_rows and its column to zero_columns. Pass 2: for each cell, if its row or column is in those sets, set it to 0. (An O(1) space version stores the markers inside the first row and column.)

3. The algorithm
   1. Two empty sets: zero_rows, zero_columns.
   2. Scan: note the row and column of every 0.
   3. Scan again: if the row or column is noted, set 0.
   4. Nothing to return (in place).

Watch it run

rows {1}, columns {1}

def set_zeroes(matrix):
    rows, columns = len(matrix), len(matrix[0])
    zero_rows, zero_columns = set(), set()
    for row in range(rows):
        for column in range(columns):
            if matrix[row][column] == 0:
                zero_rows.add(row)                       # first pass: only note, do not change
                zero_columns.add(column)
    for row in range(rows):
        for column in range(columns):
            if row in zero_rows or column in zero_columns:
                matrix[row][column] = 0                  # second pass: clear

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.