# The Zero Propagator

> One zero can change the whole picture.

Canonical URL: <https://datadriven.io/problems/the_zero_propagator>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a 2D integer matrix, zero-out every row and every column that originally contains at least one 0. Return the resulting matrix (the test harness accepts a returned matrix; in-place modification is fine too).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **set matrix zeroes** problem, probing whether a candidate can mark positions first and zero-fill second. It tests the critical insight that zeroing as you go corrupts the information needed for later decisions.

> **Trick to Solving**
>
> First pass: record which rows and columns contain zeros. Second pass: zero out those entire rows and columns. Never zero during the scan or you will create false positives.

---

### 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**

```python
def zero_propagate(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
```

> **Time and Space Complexity**
>
> **Time:** O(m * n) for two passes over the matrix.
> 
> **Space:** O(m + n) for the row and column marker sets.

> **Interviewers Watch For**
>
> Can you do this with O(1) extra space? The trick is to use the first row and first column of the matrix itself as markers, with two boolean flags to track whether the first row/column originally contained zeros.

> **Common Pitfall**
>
> Zeroing cells during the first scan creates a cascade effect. A zero introduced by the scan triggers further zeroing that was not in the original matrix.

---

## Common follow-up questions

- Can you solve this with O(1) extra space? _(Tests using the matrix's own first row and column as markers.)_
- What if the matrix was sparse (mostly zeros)? _(Tests that nearly every cell ends up zeroed, and the algorithm still works correctly.)_
- What if you needed to propagate a value other than zero? _(Tests generalizing the marker logic to any sentinel value.)_
- How would you handle this for a very large matrix stored on disk? _(Tests block-based processing with two passes over the file.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_zero_propagator)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.