Set Matrix Zeroes

▶

Steps

setup

Initialize matrix dimensions and empty sets

We determine the number of rows (m) and columns (n) and create empty sets zero_rows and zero_cols to store indices of rows and columns containing zeros.

💡 Knowing matrix size and preparing sets is essential before scanning for zeros.

Line:

m, n = len(matrix), len(matrix[0])
zero_rows = set()
zero_cols = set()

💡 Sets will efficiently track which rows and columns must be zeroed later.

traverse

Start scanning first row, first column (i=0, j=0)

We inspect element at row 0, column 0 (value 1). Since it is not zero, we do not update zero sets.

💡 Each element must be checked to find zeros.

Line:

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:

💡 Non-zero elements do not affect zero_rows or zero_cols.

traverse

Scan first row, second column (i=0, j=1)

Inspect element at (0,1) with value 1. It is not zero, so zero sets remain unchanged.

💡 Continue scanning each element to find zeros.

Line:

for j in range(n):
    if matrix[i][j] == 0:

💡 Only zero elements trigger updates to zero_rows and zero_cols.

traverse

Scan first row, third column (i=0, j=2)

Inspect element at (0,2) with value 1. It is not zero, so zero sets remain unchanged.

💡 Finish scanning first row for zeros.

Line:

for j in range(n):
    if matrix[i][j] == 0:

💡 No zeros found in first row, so no rows or columns marked yet.

traverse

Scan second row, first column (i=1, j=0)

Inspect element at (1,0) with value 1. It is not zero, so zero sets remain unchanged.

💡 Start scanning second row for zeros.

Line:

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:

💡 Continue scanning until zero is found.

traverse

Scan second row, second column (i=1, j=1) - zero found

Inspect element at (1,1) with value 0. We add row 1 and column 1 to zero_rows and zero_cols sets.

💡 Finding a zero triggers recording its row and column indices.

Line:

if matrix[i][j] == 0:
    zero_rows.add(i)
    zero_cols.add(j)

💡 Marking row and column for zeroing later.

traverse

Scan second row, third column (i=1, j=2)

Inspect element at (1,2) with value 1. It is not zero, so zero sets remain unchanged.

💡 Finish scanning second row.

Line:

for j in range(n):
    if matrix[i][j] == 0:

💡 Only one zero in this row affects zero sets.

traverse

Scan third row, first column (i=2, j=0)

Inspect element at (2,0) with value 1. It is not zero, so zero sets remain unchanged.

💡 Start scanning third row for zeros.

Line:

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:

💡 No new zeros found in third row.

traverse

Scan third row, second column (i=2, j=1)

Inspect element at (2,1) with value 1. It is not zero, so zero sets remain unchanged.

💡 Continue scanning third row.

Line:

for j in range(n):
    if matrix[i][j] == 0:

💡 No zeros found in this column except previously recorded.

traverse

Scan third row, third column (i=2, j=2)

Inspect element at (2,2) with value 1. It is not zero, so zero sets remain unchanged.

💡 Finish scanning matrix for zeros.

Line:

for j in range(n):
    if matrix[i][j] == 0:

💡 All zero positions recorded; ready to zero rows and columns.

insert

Start zeroing matrix elements based on zero sets (i=0, j=0)

We begin second traversal to zero elements. At (0,0), row 0 and column 0 are not in zero sets, so value remains 1.

💡 Second pass applies zeroing based on recorded rows and columns.

Line:

for i in range(m):
    for j in range(n):
        if i in zero_rows or j in zero_cols:
            matrix[i][j] = 0

💡 Only elements in marked rows or columns become zero.

insert

Zero element at (0,1) because column 1 is marked

At (0,1), column 1 is in zero_cols, so we set matrix[0][1] to zero.

💡 Any element in a zero-marked column must be zeroed.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Column zeroing affects all rows in that column.

insert

No zeroing at (0,2) since row 0 and col 2 not marked

At (0,2), neither row 0 nor column 2 is in zero sets, so value remains 1.

💡 Elements outside marked rows and columns remain unchanged.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Zeroing is selective based on recorded indices.

insert

Zero entire second row (i=1, j=0)

Row 1 is in zero_rows, so element at (1,0) is set to zero.

💡 All elements in zero-marked rows become zero.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Row zeroing affects all columns in that row.

insert

Zero element at (1,1) already zero

At (1,1), element is already zero; no change needed.

💡 Zeroing an already zero element is idempotent.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Zeroing operation is safe even if element is zero.

insert

Zero element at (1,2) due to row 1

At (1,2), row 1 is in zero_rows, so element is set to zero.

💡 Complete zeroing of the entire second row.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Row zeroing affects all columns in that row.

insert

Zero element at (2,0) no zeroing needed

At (2,0), row 2 and column 0 are not marked, so element remains 1.

💡 Only marked rows or columns are zeroed.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Elements outside zero sets remain unchanged.

insert

Zero element at (2,1) due to column 1

At (2,1), column 1 is in zero_cols, so element is set to zero.

💡 Column zeroing affects all rows in that column.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Column zeroing applies across all rows.

insert

No zeroing at (2,2) since row 2 and col 2 not marked

At (2,2), neither row 2 nor column 2 is in zero sets, so element remains 1.

💡 Finish zeroing process.

Line:

if i in zero_rows or j in zero_cols:
    matrix[i][j] = 0

💡 Final elements outside zero sets remain unchanged.

reconstruct

Final matrix after zeroing rows and columns

The matrix has been updated in-place with zeros in all elements of row 1 and column 1, as required.

💡 The final matrix reflects the zeroing logic applied correctly.

Line:

return matrix

💡 The algorithm successfully zeroed rows and columns containing zeros without extra matrix space.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])  # STEP 1
    zero_rows = set()  # STEP 1
    zero_cols = set()  # STEP 1
    for i in range(m):  # STEP 2-10
        for j in range(n):  # STEP 2-10
            if matrix[i][j] == 0:  # STEP 6
                zero_rows.add(i)  # STEP 6
                zero_cols.add(j)  # STEP 6
    for i in range(m):  # STEP 11-19
        for j in range(n):  # STEP 11-19
            if i in zero_rows or j in zero_cols:  # STEP 12,14,16,18
                matrix[i][j] = 0  # STEP 12,14,16,18

if __name__ == '__main__':
    mat = [[1,1,1],[1,0,1],[1,1,1]]
    setZeroes(mat)
    print(mat)  # STEP 20

📊

Set Matrix Zeroes - Watch the Algorithm Execute, Step by Step

Watching each pointer and set update live reveals how the algorithm efficiently tracks zero positions and applies changes without extra matrix space.

setup

1

0

1

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[],"zero_cols":[]}

compare

j

1

0

1

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[],"zero_cols":[]}

compare

i

1

0

j

1

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[],"zero_cols":[]}

compare

i

1

0

1

1

j

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[],"zero_cols":[]}

compare

j

1

0

i

1

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[],"zero_cols":[]}

record

1

0

j

1

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

1

0

i

1

1

j

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

j

1

0

1

1

i

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

1

0

j

1

1

i

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

1

0

1

1

j

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

j

1

0

1

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

swap

i

1

0

j

0

1

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

i

1

0

0

1

j

1

2

1

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

swap

j

1

0

i

0

1

1

2

0

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

1

0

j

0

1

1

2

0

3

0

4

1

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

swap

1

0

i

0

1

j

1

2

0

3

0

4

0

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

j

1

0

0

1

i

1

2

0

3

0

4

0

5

1

6

1

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

swap

1

0

j

0

1

i

1

2

0

3

0

4

0

5

1

6

0

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

compare

1

0

0

1

j

1

2

0

3

0

4

0

5

1

6

0

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

reconstruct

1

0

0

1

1

2

0

3

0

4

0

5

1

6

0

7

1

8

Result: {"zero_rows":[1],"zero_cols":[1]}

Key Takeaways

✓ Tracking zero rows and columns with sets allows efficient in-place zeroing without extra matrix space.

This insight is hard to see from code alone because the sets' role is abstract; visualization shows exactly which rows and columns are affected.

✓ The two-pass approach separates detection of zeros from modification, preventing premature overwriting.

Watching the traversal and zeroing phases distinctly clarifies why the algorithm avoids corrupting data during scanning.

✓ Zeroing only occurs if the current element's row or column is marked, demonstrating selective updates.

Seeing each element checked against zero sets helps understand the conditional logic that governs zeroing.

Practice

1. Given the following Python code for diagonal traversal, what is the final output when the input matrix is [[1,2,3],[4,5,6],[7,8,9]]?

easy

A. [1,4,2,3,5,7,8,6,9]

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

C. [1,2,3,4,5,6,7,8,9]

D. [1,2,4,5,3,6,7,8,9]

Solution

1. Step 1: Trace diagonal 0 (d=0)

   r_start=0, r_end=0, even diagonal -> traverse from r_end down to r_start: mat[0][0]=1

2. Step 2: Trace diagonal 1 (d=1)

   r_start=0, r_end=1, odd diagonal -> traverse from r_start up to r_end: mat[0][1]=2, mat[1][0]=4

3. Step 3: Trace diagonal 2 (d=2)

   r_start=0, r_end=2, even diagonal -> traverse from r_end down to r_start: mat[2][0]=7, mat[1][1]=5, mat[0][2]=3

4. Step 4: Trace diagonal 3 (d=3)

   r_start=1, r_end=2, odd diagonal -> traverse from r_start up to r_end: mat[1][2]=6, mat[2][1]=8

5. Step 5: Trace diagonal 4 (d=4)

   r_start=2, r_end=2, even diagonal -> traverse from r_end down to r_start: mat[2][2]=9

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Output matches expected zigzag diagonal order [OK]

Hint: Even diagonals traverse down, odd diagonals traverse up [OK]

Common Mistakes:

• Mixing traversal direction for even/odd diagonals

2. Consider the following Python function that computes the sum of the diagonals of a square matrix:

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total -= mat[n//2][n//2]
    return total

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(diagonalSum(matrix))

What is the value of total after the loop completes but before the if-condition is applied?

easy

A. 15

B. 25

C. 30

D. 45

Solution

1. Step 1: Trace the loop iterations

   For i=0: total = 0 + mat[0][0] + mat[0][2] = 0 + 1 + 3 = 4 For i=1: total = 4 + mat[1][1] + mat[1][1] = 4 + 5 + 5 = 14 For i=2: total = 14 + mat[2][2] + mat[2][0] = 14 + 9 + 7 = 30

2. Step 2: Note that the if-condition has not yet been applied

   The total before subtracting the center element is 30.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of diagonals before center correction is 30 [OK]

Hint: Sum both diagonals first, then adjust center if needed [OK]

Common Mistakes:

• Forgetting to subtract center element once
• Double counting center element
• Off-by-one in indices

3. You need to fill an n x n matrix with numbers from 1 to n² in a pattern that starts at the top-left corner and proceeds in a clockwise spiral moving outward. Which approach guarantees filling all cells correctly without revisiting or skipping any cell?

easy

A. Greedy approach filling rows and columns independently without tracking boundaries

B. Dynamic programming to store partial sums and fill matrix based on subproblems

C. Directional simulation with boundary shrinking and cycling through directions

D. Sorting all numbers and placing them diagonally from top-left to bottom-right

Solution

1. Step 1: Understand the problem constraints

   The matrix must be filled in a spiral order, visiting each cell exactly once in a clockwise manner.

2. Step 2: Identify the approach that tracks boundaries and direction

   Directional simulation with boundary shrinking ensures that after filling one side, boundaries are updated to avoid revisiting cells, and directions cycle through right, down, left, and up correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary shrinking prevents overwriting and ensures full coverage [OK]

Hint: Track boundaries and directions to avoid revisits [OK]

Common Mistakes:

• Assuming greedy row/column fills without boundary checks works
• Confusing DP with spiral traversal
• Ignoring direction cycling leads to incomplete fills

4. Suppose the problem changes: you want to find the top 3 maximum hourglass sums in the matrix instead of just the maximum. Which modification to the sliding window approach is correct and efficient?

hard

A. Store all hourglass sums in a list and sort it at the end to pick top 3.

B. Run the sliding window 3 times, each time removing the previously found max hourglass from the matrix.

C. Maintain a min-heap of size 3 to track top sums while sliding through the matrix.

D. Use dynamic programming to store maximum sums for all submatrices and pick top 3.

Solution

1. Step 1: Understand the need to track multiple top sums efficiently

   Storing all sums and sorting is inefficient for large matrices.

2. Step 2: Use a min-heap of fixed size 3

   Insert sums as you compute; if heap size exceeds 3, pop smallest. This keeps top 3 sums efficiently.

3. Step 3: Reject other options

   Sorting all sums (A) is costly; repeated removal (C) is complex and incorrect; DP (D) is unnecessary and inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap maintains top K sums in O(n*m*logK) time [OK]

Hint: Use min-heap to track top K sums efficiently [OK]

Common Mistakes:

• Sorting all sums after computation
• Repeatedly removing max sums from matrix
• Using DP unnecessarily

5. Suppose the Sudoku validation problem is extended so that the board size is variable (N x N), where N is a perfect square (e.g., 4x4, 16x16), and digits range from 1 to N. Which of the following modifications to the bitmasking approach is necessary to correctly validate such boards?

hard

A. Use larger integer types or multiple integers to represent bitmasks since N can exceed 32 bits.

B. Keep the same 9x9 fixed-size arrays and bitmasks since the logic is identical regardless of N.

C. Replace bitmasking with hash sets because bitmasking only works for 9x9 boards.

D. Only check rows and columns; boxes are not needed for variable-sized boards.

Solution

1. Step 1: Understand bitmask size limitation

   Bitmasking uses bits to represent digits; for N > 32, a single integer is insufficient.

2. Step 2: Modify data structures accordingly

   Use larger integer types (e.g., 64-bit) or multiple integers/arrays to represent bitmasks for larger N.

3. Step 3: Confirm boxes must still be checked

   Boxes remain part of the constraints; logic must adapt to variable box sizes.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bitmask size must scale with N to represent all digits [OK]

Hint: Bitmask size must scale with board size N [OK]

Common Mistakes:

• Assuming fixed 9x9 arrays suffice
• Dropping box checks
• Thinking bitmasking can't scale at all