The Zero Propagator

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Fox Creek Veterinary Hospital - Wildwood

Problem

You're cleaning a 2D integer matrix from a data export where a 0 marks a bad reading. Zero out every row and every column that originally contained a 0, and return the cleaned matrix.

One zero can change the whole picture.

Example 1

Input:

matrix = [[1,2,3],[4,0,6],[7,8,9]]

Output:

[[1,0,3],[0,0,0],[7,0,9]]

Example 2

Input:

matrix = [[1,2,0],[3,4,5]]

Output:

[[0,0,0],[3,4,0]]

Worked solution and explanation

Why this problem exists in real interviews

Strip the business costume and this is a detection-then-mutation problem: you have to find every original zero before you change a single cell. Anyone can write the two nested loops. The trick is refusing to zero anything during the scan, because the instant you blank a row, those fresh zeros look exactly like originals and cascade. Do the marking and the writing in the same pass and you'll blank the whole matrix instead of the rows and columns you meant to.

Break down the requirements

Step 1: Scan the matrix and record zero positions

Collect the set of rows and columns that contain at least one zero.

Step 2: Zero out marked rows and columns in a second pass

For each cell, if its row or column is in the marked sets, set it to zero.

The solution

Two-pass scan with row/column marker sets
def set_zeroes(matrix: list) -> list:
    if not matrix or not matrix[0]:
        return matrix
    rows = len(matrix)
    cols = len(matrix[0])
    zero_rows = set()
    zero_cols = set()
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)
    for r in range(rows):
        for c in range(cols):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0
    return matrix

Common follow-up questions