Set Matrix Zeroes In Place in DSA Python

Mental Model

When a cell in a matrix is zero, set its entire row and column to zero without using extra space.

Analogy: Imagine a grid of lights where if one light goes off, the entire row and column of lights must also go off, but you only have one chance to mark which rows and columns to turn off without extra sticky notes.

Matrix before:
1 1 1
1 0 1
1 1 1

We want to mark rows and columns to zero without extra space.

Dry Run Walkthrough

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

Goal: Set entire row and column to zero for every cell that is zero, modifying matrix in place.

Step 1: Check first row and first column for zeros to remember if they need zeroing later

First row: 1 1 1
First column: 1 1 1

Why: We need to know if first row or column should be zeroed later since we will use them as markers

Step 2: Traverse matrix from row 1 and col 1, mark zeros in first row and column

Matrix after marking:
1 0 1
0 0 1
1 1 1

Why: Mark rows and columns to zero by setting first cell of that row and column to zero

Step 3: Zero rows based on marks in first column

Matrix after zeroing rows:
1 0 1
0 0 0
1 1 1

Why: Rows with zero in first column must be zeroed

Step 4: Zero columns based on marks in first row

Matrix after zeroing columns:
1 0 1
0 0 0
1 0 1

Why: Columns with zero in first row must be zeroed

Step 5: Zero first row and first column if needed (none in this example)

Final matrix:
1 0 1
0 0 0
1 0 1

Why: Apply zeroing to first row and column if they originally had zeros

Result:

1 0 1
0 0 0
1 0 1

Annotated Code

DSA Python

from typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
        first_col_zero = any(matrix[i][0] == 0 for i in range(rows))

        # Mark zeros on first row and column
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0  # mark row
                    matrix[0][j] = 0  # mark column

        # Zero rows based on marks
        for i in range(1, rows):
            if matrix[i][0] == 0:
                for j in range(cols):
                    matrix[i][j] = 0

        # Zero columns based on marks
        for j in range(1, cols):
            if matrix[0][j] == 0:
                for i in range(rows):
                    matrix[i][j] = 0

        # Zero first row if needed
        if first_row_zero:
            for j in range(cols):
                matrix[0][j] = 0

        # Zero first column if needed
        if first_col_zero:
            for i in range(rows):
                matrix[i][0] = 0


# Driver code
matrix = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]

sol = Solution()
sol.setZeroes(matrix)
for row in matrix:
    print(' '.join(str(x) for x in row))

first_row_zero = any(matrix[0][j] == 0 for j in range(cols))

Check if first row has any zero to handle separately later

first_col_zero = any(matrix[i][0] == 0 for i in range(rows))

Check if first column has any zero to handle separately later

for i in range(1, rows): for j in range(1, cols): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0

Mark rows and columns to be zeroed by setting first cell in row and column to zero

for i in range(1, rows): if matrix[i][0] == 0: for j in range(cols): matrix[i][j] = 0

Zero entire row if marked

for j in range(1, cols): if matrix[0][j] == 0: for i in range(rows): matrix[i][j] = 0

Zero entire column if marked

if first_row_zero: for j in range(cols): matrix[0][j] = 0

Zero first row if originally had zero

if first_col_zero: for i in range(rows): matrix[i][0] = 0

Zero first column if originally had zero

Output

1 0 1

0 0 0

1 0 1

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each cell is visited a constant number of times

Space: O(1) because we use the matrix itself for marking without extra space

vs Alternative: Naive approach uses extra O(m+n) space for row and column markers, this approach saves space by using first row and column as markers

Edge Cases

Matrix with no zeros

Matrix remains unchanged

DSA Python

first_row_zero = any(matrix[0][j] == 0 for j in range(cols))

Matrix with zero in first row and first column

First row and column are zeroed correctly after marking

DSA Python

if first_row_zero:
    for j in range(cols):
        matrix[0][j] = 0

Matrix with single element zero

Single element matrix zeroed correctly

DSA Python

first_row_zero = any(matrix[0][j] == 0 for j in range(cols))

When to Use This Pattern

When you need to set entire rows and columns to zero based on zero cells without extra space, use the first row and column as markers to track zeroing.

Common Mistakes

Mistake: Using extra arrays for marking rows and columns, increasing space complexity
Fix: Use the first row and first column of the matrix itself as markers to save space

Mistake: Zeroing first row and column too early, losing marker information
Fix: Check and store if first row and column need zeroing before marking, then zero them last

Summary

Sets entire rows and columns to zero in a matrix if any cell in them is zero, modifying the matrix in place.

Use when you want to save space and avoid extra memory while zeroing rows and columns based on zero cells.

The key insight is to use the first row and first column as markers to track which rows and columns to zero.

Practice

1. What is the main goal of the Set Matrix Zeroes In Place problem?

easy

A. Find the sum of all elements in the matrix.

B. Modify the matrix so that if an element is 0, its entire row and column become 0.

C. Sort each row of the matrix in ascending order.

D. Transpose the matrix without changing its elements.

Solution

1. Step 1: Understand the problem requirement

   The problem asks to change the matrix so that if any element is zero, all elements in that element's row and column become zero.

2. Step 2: Identify the correct description

   Modify the matrix so that if an element is 0, its entire row and column become 0. exactly describes this transformation, while others describe unrelated operations.

3. Final Answer:

   Modify the matrix so that if an element is 0, its entire row and column become 0. -> Option B

4. Quick Check:

   Set matrix zeroes means zero rows and columns [OK]

Hint: Remember zero means zero entire row and column [OK]

Common Mistakes:

• Confusing with matrix transpose
• Thinking only the zero element changes
• Trying to sum or sort instead

2. Which of the following Python code snippets correctly initializes a 3x3 matrix with all zeros?

easy

A. matrix = [[0]*3]*3

B. matrix = [0,0,0]*3

C. matrix = [0]*3 for _ in range(3)

D. matrix = [[0 for _ in range(3)] for _ in range(3)]

Solution

1. Step 1: Analyze each initialization method

   matrix = [[0]*3]*3 creates shallow copies of the same row, causing changes in one row to affect others. matrix = [[0 for _ in range(3)] for _ in range(3)] creates independent rows correctly. matrix = [0]*3 for _ in range(3) is invalid syntax. matrix = [0,0,0]*3 creates a flat list, not a matrix.

2. Step 2: Choose the correct matrix initialization

   Only matrix = [[0 for _ in range(3)] for _ in range(3)] correctly creates a 3x3 matrix with independent rows filled with zeros.

3. Final Answer:

   matrix = [[0 for _ in range(3)] for _ in range(3)] -> Option D

4. Quick Check:

   Use nested list comprehension for independent rows [OK]

Hint: Use nested list comprehension for 2D matrix [OK]

Common Mistakes:

• Using [[0]*3]*3 causes shared references
• Incorrect syntax in option C
• Flat list instead of 2D matrix

3. What will be the matrix after applying the Set Matrix Zeroes In Place logic on this matrix?

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

medium

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

B. [[1, 2, 3], [4, 0, 6], [7, 8, 9]]

C. [[1, 2, 3], [0, 0, 0], [7, 8, 9]]

D. [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Solution

1. Step 1: Identify zero positions

   The zero is at position (1,1) (second row, second column).

2. Step 2: Set entire row 1 and column 1 to zero

   Row 1 becomes [0,0,0]. Column 1 elements at rows 0 and 2 become zero, changing matrix to [[1,0,3],[0,0,0],[7,0,9]].

3. Final Answer:

   [[1, 0, 3], [0, 0, 0], [7, 0, 9]] -> Option A

4. Quick Check:

   Zero at (1,1) zeroes row 1 and column 1 [OK]

Hint: Zero row and column for each zero element [OK]

Common Mistakes:

• Not zeroing the entire column
• Changing elements not in zero row/column
• Confusing row and column indices

4. Given this code snippet to set matrix zeroes in place, what is the main bug?

def setZeroes(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    zero_rows = set()
    zero_cols = set()
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                zero_rows.add(i)
                zero_cols.add(j)
    for i in zero_rows:
        for j in range(cols):
            matrix[i][j] = 0
    for j in zero_cols:
        for i in range(rows):
            matrix[i][j] = 0

medium

A. It misses zeroing the diagonal elements.

B. It modifies the matrix before identifying all zeroes.

C. It uses extra space, not in-place modification.

D. It does not handle empty matrices.

Solution

1. Step 1: Analyze space usage

   The code uses sets zero_rows and zero_cols to store indices, which uses extra space proportional to matrix size.

2. Step 2: Understand in-place requirement

   The problem requires modifying the matrix without extra space (in-place). Using sets violates this.

3. Final Answer:

   It uses extra space, not in-place modification. -> Option C

4. Quick Check:

   Extra sets mean not in-place [OK]

Hint: In-place means no extra sets or arrays [OK]

Common Mistakes:

• Ignoring extra space used by sets
• Thinking diagonal needs special handling
• Assuming empty matrix causes error here

5. How can you modify the matrix [[1,2,3],[4,0,6],[7,8,9]] in place to set zeroes without using extra space for rows and columns? Which approach is correct?

hard

A. Use first row and first column as markers to track zero rows and columns, then update matrix accordingly.

B. Create two separate lists to store zero rows and columns, then update matrix.

C. Copy the matrix, modify the copy, then replace original matrix.

D. Only zero the rows where zero is found, ignore columns.

Solution

1. Step 1: Use first row and column as markers

   Mark zeros in first row and column to remember which rows and columns to zero later, avoiding extra space.

2. Step 2: Update matrix based on markers

   After marking, iterate matrix to set zeros in rows and columns indicated by markers, then handle first row and column separately.

3. Final Answer:

   Use first row and first column as markers to track zero rows and columns, then update matrix accordingly. -> Option A

4. Quick Check:

   First row/column markers enable in-place zeroing [OK]

Hint: Use matrix edges as markers to avoid extra space [OK]

Common Mistakes:

• Using extra lists violates in-place rule
• Copying matrix wastes space
• Ignoring zero columns leads to wrong result