\

Set Matrix Zeroes

Difficulty: N/A | Solved: December 20, 2025

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

Example 1:

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

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Brainstorming

so the first things that comes to mind is finding the element 0 in the 2D array. for that we have to go sequentially row by row col by col we check and make sure that we only trigger the set_zero helper function

once we find an element we can then set the elements to zero for its row and col maybe we can do it recursively as well but the problem with recursion is its dumb and we cannot control its direction

the other challenge is i have to do it inplace for that i think we can use hashing

Optimal Solution

You’ve had two excellent initial thoughts. Let’s analyze them.

Idea #1: The Naive “Find and Set” Approach

“go sequentially… once we find an element we can then set the elements to zero for its row and col”

This is a great brute-force starting point.

# Naive approach
for r in range(rows):
    for c in range(cols):
        if matrix[r][c] == 0:
            # Found a zero! Now set its row and col to zero.
            set_row_to_zero(r)
            set_col_to_zero(c)

Let’s trace this with an example: [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

  1. The loops run. At (1, 1), we find a 0.
  2. We call set_row_to_zero(1). The matrix becomes [[1, 1, 1], [0, 0, 0], [1, 1, 1]].
  3. We call set_col_to_zero(1). The matrix becomes [[1, 0, 1], [0, 0, 0], [1, 0, 1]].
  4. The Problem: The for loop continues. At (1, 2), the value is now 0 (it was originally 1). Our code will find this new zero and then incorrectly proceed to zero out row 1 (again) and column 2.

Question 1: This “chain reaction” corrupts our original information. How can we know which zeroes were the original ones and which ones were newly created?

Idea #2: Using Hashing (Extra Space)

“i have to do it inplace for that i think we can use hashing”

This is the perfect solution to the problem identified in Idea #1. Instead of changing the matrix as we scan it, we can use extra storage to just record which rows and columns need to be zeroed out.

  • Pass 1: Record.

    • Create a hash set for rows to be zeroed (rows_to_zero).
    • Create a hash set for columns to be zeroed (cols_to_zero).
    • Iterate through the entire matrix. If you find a zero at (r, c), you do:
      • rows_to_zero.add(r)
      • cols_to_zero.add(c)

  • Pass 2: Modify.

    • Iterate through the entire matrix again. For each cell (r, c):
      • if r in rows_to_zero or c in cols_to_zero:
        • matrix[r][c] = 0

This approach is correct! It solves the chain reaction problem.

Question 2: What is the space complexity of this hashing/two-set approach? The problem asks for an in-place solution, which is usually a hint for O(1) space. How can we do better?

  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-10 16:00) - (end:: 2025-12-10 16:20) so essentially then we are doing 2 pass solution in the first pass we try to find the rows that we have to set to 0 and then col be we have to set to 0 and in the second pass we just set it to zero
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

rows_to_zero = set()

cols_to_zero = set()

M = len(matrix)
N = len(matrix[0])

# first pass to gather information about where is zero present
for i in range(M):
	for j in range(N):
		if matrix[i][j] == 0:
			rows_to_zero.add(i) # row to be set to zero
			cols_to_zero.add(j) # col to be set to zero

for i in range(M):
	for j in range(N):
		if i in rows_to_zero or j in cols_to_zero:
			matrix[i][j] = 0

print(matrix)

The O(1) Space Solution

Your hashing approach is the key. It works because it separates the “recording” phase from the “modifying” phase.
To get to O(1) space, we need to find a place to “record” this information within the matrix itself.

Your Prompt:

How could you use the first row and column as your hash sets to get to O(1) space?

Let’s use the first row and first column as our “memory.”

Proposed Logic (Pass 1 - Recording):

  • Iterate through the matrix, but skip the first row and first column for now (i.e., from r=1 to M-1 and c=1 to N-1).

  • If you find a zero at matrix`[r][c]:

    • Instead of rows_to_zero.add(r), we can use the first element of that row as a marker. Let’s set matrix`[r][0] = 0.

    • Instead of cols_to_zero.add(c), we can use the first element of that column as a marker. Let’s set matrix`[0][c] = 0.

After this first pass, the first row and first column now contain “markers” indicating which of the inner rows/columns need to be zeroed out.

The Problem / Edge Case:
What about the first row and first column themselves? If matrix[0][0] is now 0, does that mean the original value was 0, or that it was turned into a marker by some other cell? We’ve “contaminated” our memory.

If we find a zero at (3, 4), we set matrix[3][0] = 0 and matrix[0][4] = 0.
If we find a zero at (0, 2), we can’t set matrix[0][0] = 0 because that would wrongly signal that row 0 and column 0 need to be zeroed.

We need a way to separately track if the original first row and first column themselves contained a zero.

Question: How could you use just two extra boolean variables to keep track of the status of the original first row and first column before you start using them as markers?

(Prompt): Describe a complete, multi-pass algorithm that uses the first row and first column as its main “memory” and two extra boolean variables to handle the edge case.

  1. Pass 0 (Pre-computation): What should you check for before you start the main loop?
  2. Pass 1 (Marking): How do you iterate and set your markers in the first row/column?
  3. Pass 2 (Modifying the inner matrix): How do you use your markers to set the inner part of the matrix to zero?
  4. Pass 3 (Modifying the first row/col): How do you use your boolean flags from Pass 0 to clean up the first row and column at the very end?

The O(1) Space Algorithm:

Step 1: Pre-computation / Check First Row & Col

  • Create two boolean flags: first_row_has_zero = False, first_col_has_zero = False.
  • Iterate through the first row (matrix[0][...]). If you find a 0, set first_row_has_zero = True and break the loop.
  • Iterate through the first column (matrix[...][0]). If you find a 0, set first_col_has_zero = True and break the loop.
    • (These two loops establish the ground truth for the first row/col before we start overwriting them).

Step 2: Marking (Using the first row/col as memory)

  • Iterate through the inner matrix (from row=1 to M-1, and col=1 to N-1).
  • If matrix[r][c] == 0:
    • Set matrix[r][0] = 0.
    • Set matrix[0][c] = 0.

Step 3: Modifying the Inner Matrix

  • Iterate through the inner matrix again (from row=1 to M-1, and col=1 to N-1).

  • For each cell (r, c), check its markers:

    • if matrix[r][0] == 0 or matrix[0][c] == 0:
      • matrix[r][c] = 0.

Step 4: Modifying the First Row & Col (Using the flags)

  • This is the final cleanup step.

  • if first_row_has_zero:

    • Iterate through the first row and set all its elements to 0.

  • if first_col_has_zero:

    • Iterate through the first column and set all its elements to 0.

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

M = len(matrix) # rows
N = len(matrix[0]) # columns

first_row_has_zero = False
first_col_has_zero = False

# first pass to check if the first row or first col has zero
# first row
for i in range (M):
	if matrix[i][0] == 0:
		first_col_has_zero = True

# first column
for j in range(N):
	if matrix[0][j] == 0:
		first_row_has_zero = True

# first main loop to record zeros

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

# second main loop to update the inner matrix for zero

for i in range(1,M):
	for j in range(1,N):
		if matrix[i][0] == 0 or matrix[0][j] ==0:
			matrix[i][j] = 0

# third check to set first row and columns to zero
if first_row_has_zero:
	for i in range (M):
		matrix[i][0] = 0

if first_col_has_zero:
	for j in range(N):
		matrix[0][j] = 0
		

print(matrix)

Final Solution

def set_zeroes(matrix):
    if not matrix or not matrix[0]:
        return

    M = len(matrix)
    N = len(matrix[0])

    first_row_has_zero = False
    first_col_has_zero = False

    # 1. Pre-computation: Check if the original first row/col need to be zeroed.
    for j in range(N):
        if matrix[0][j] == 0:
            first_row_has_zero = True
            break

    for i in range(M):
        if matrix[i][0] == 0:
            first_col_has_zero = True
            break

    # 2. Marking: Use the first row/col as memory for the inner matrix.
    for i in range(1, M):
        for j in range(1, N):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    # 3. Modifying: Set the inner matrix to zero based on the markers.
    for i in range(1, M):
        for j in range(1, N):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    # 4. Final Cleanup: Set the first row/col to zero if needed.
    if first_row_has_zero:
        for j in range(N):
            matrix[0][j] = 0

    if first_col_has_zero:
        for i in range(M):
            matrix[i][0] = 0

print(matrix)
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-10 16:24) - (end:: 2025-12-10 16:54)