Problem Description

You are given an m x n integer matrix. Your task is to modify the matrix such that if any element in the matrix is 0, then you must set its entire row and entire column to 0s.

The key requirement is that you must perform this operation in place, meaning you should modify the original matrix directly without using additional matrix space.

For example, if you have a matrix like:

1  1  1
1  0  1
1  1  1

After applying the operation, it should become:

1  0  1
0  0  0
1  0  1

The second row and second column are all set to 0 because there was a 0 at position [1][1].

The solution uses two boolean arrays row and col to track which rows and columns need to be zeroed. First, it scans through the entire matrix to identify all positions containing 0, marking the corresponding rows and columns. Then, it makes a second pass through the matrix, setting any element to 0 if its row or column was marked.

The time complexity is O(m × n) where m is the number of rows and n is the number of columns, as we traverse the matrix twice. The space complexity is O(m + n) for the two marking arrays.

Intuition

The challenge here is that we need to set entire rows and columns to 0, but we can't do it immediately when we find a 0 because that would interfere with our scanning process. If we start setting zeros right away, we might lose information about which zeros were originally in the matrix versus which ones we just added.

For instance, if we find a 0 at position [1][1] and immediately set the entire row and column to 0, when we continue scanning and reach position [1][2], we'll see a 0 there (which we just set), but we won't know if it was originally 0 or not. This could lead to incorrectly zeroing out additional rows and columns.

The key insight is to separate the detection phase from the modification phase. We need to first identify all the rows and columns that need to be zeroed, then apply the changes in a second pass.

Think of it like marking items on a checklist before taking action. We need to:

1. First, walk through the entire matrix and make a note of which rows and columns contain at least one 0
2. Then, go through the matrix again and actually perform the zeroing operation based on our notes

This leads us to use two auxiliary arrays: row[i] tells us whether row i should be zeroed, and col[j] tells us whether column j should be zeroed. During the first pass, whenever we encounter matrix[i][j] == 0, we mark row[i] = True and col[j] = True. In the second pass, for each position [i][j], if either row[i] or col[j] is True, we set matrix[i][j] = 0.

This two-pass approach ensures we preserve all the original information we need before making any modifications, avoiding the problem of losing track of which zeros were original.

Solution Approach

Following the array marking strategy, we implement the solution using two boolean arrays to track which rows and columns need to be zeroed.

Step 1: Initialize marking arrays

m, n = len(matrix), len(matrix[0])
row = [False] * m
col = [False] * n

We create two boolean arrays: row of size m (number of rows) and col of size n (number of columns). Initially, all values are False, meaning no rows or columns are marked for zeroing yet.

Step 2: First pass - Mark rows and columns

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

We traverse the entire matrix once. Whenever we encounter a 0 at position [i][j], we mark both:

• row[i] = True to indicate that row i contains at least one zero
• col[j] = True to indicate that column j contains at least one zero

This marking process preserves the information about all original zeros in the matrix without modifying the matrix itself yet.

Step 3: Second pass - Apply the zeros

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

We traverse the matrix again. For each position [i][j], we check:

• If row[i] is True (meaning row i should be zeroed), OR
• If col[j] is True (meaning column j should be zeroed)

If either condition is true, we set matrix[i][j] = 0.

The beauty of this approach is that it cleanly separates the detection phase from the modification phase, ensuring we don't lose any information about the original zeros in the matrix. The use of separate marking arrays makes the logic straightforward and easy to understand.

Time Complexity: O(m × n) - We traverse the matrix twice
Space Complexity: O(m + n) - We use two auxiliary arrays of sizes m and n

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works step by step.

Initial Matrix:

[1, 2, 3, 4]
[5, 0, 7, 8]
[9, 10, 11, 12]

Step 1: Initialize marking arrays

• m = 3 (rows), n = 4 (columns)
• row = [False, False, False]
• col = [False, False, False, False]

Step 2: First pass - Mark rows and columns

We scan through each element:

• Position [0][0]: value is 1 (not zero), continue
• Position [0][1]: value is 2 (not zero), continue
• Position [0][2]: value is 3 (not zero), continue
• Position [0][3]: value is 4 (not zero), continue
• Position [1][0]: value is 5 (not zero), continue
• Position [1][1]: value is 0 → Mark row[1] = True and col[1] = True
• Position [1][2]: value is 7 (not zero), continue
• Position [1][3]: value is 8 (not zero), continue
• Position [2][0]: value is 9 (not zero), continue
• Position [2][1]: value is 10 (not zero), continue
• Position [2][2]: value is 11 (not zero), continue
• Position [2][3]: value is 12 (not zero), continue

After first pass:

• row = [False, True, False] (row 1 contains a zero)
• col = [False, True, False, False] (column 1 contains a zero)

Step 3: Second pass - Apply the zeros

Now we check each position and set to zero if its row or column is marked:

• Position [0][0]: row[0] = False, col[0] = False → Keep value 1
• Position [0][1]: row[0] = False, col[1] = True → Set to 0
• Position [0][2]: row[0] = False, col[2] = False → Keep value 3
• Position [0][3]: row[0] = False, col[3] = False → Keep value 4
• Position [1][0]: row[1] = True, col[0] = False → Set to 0
• Position [1][1]: row[1] = True, col[1] = True → Set to 0
• Position [1][2]: row[1] = True, col[2] = False → Set to 0
• Position [1][3]: row[1] = True, col[3] = False → Set to 0
• Position [2][0]: row[2] = False, col[0] = False → Keep value 9
• Position [2][1]: row[2] = False, col[1] = True → Set to 0
• Position [2][2]: row[2] = False, col[2] = False → Keep value 11
• Position [2][3]: row[2] = False, col[3] = False → Keep value 12

Final Matrix:

[1, 0, 3, 4]
[0, 0, 0, 0]
[9, 0, 11, 12]

The entire row 1 and column 1 have been set to zero, as required. Note how the two-pass approach ensures we don't accidentally zero out additional rows or columns by preserving the original zero locations in our marking arrays before making any modifications.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two nested loops that iterate through the entire matrix:

• The first nested loop scans all m × n elements to identify which rows and columns contain zeros, taking O(m × n) time.
• The second nested loop iterates through all m × n elements again to set the appropriate cells to zero based on the row and column markers, also taking O(m × n) time.
• The total time complexity is O(m × n) + O(m × n) = O(m × n).

Space Complexity: O(m + n)

The algorithm uses two auxiliary arrays:

• row: A boolean array of size m to track which rows contain at least one zero.
• col: A boolean array of size n to track which columns contain at least one zero.
• The total extra space used is O(m) + O(n) = O(m + n).

Where m and n are the number of rows and columns of the matrix respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Modifying the matrix during the first scan

The Problem: A common mistake is attempting to set zeros immediately when finding a zero element during the first scan:

# INCORRECT approach
for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            # Setting zeros immediately - DON'T DO THIS!
            for k in range(n):
                matrix[i][k] = 0
            for k in range(m):
                matrix[k][j] = 0

This approach fails because it destroys the original information in the matrix. Once you set a row or column to zero, you can't distinguish between:

• Original zeros that should trigger row/column zeroing
• Newly added zeros from the modification

Example of the issue:

Original:     After first zero found:    Final (incorrect):
1  0  1       0  0  0                    0  0  0
1  1  1  -->  1  0  1               -->  0  0  0
1  1  0       1  0  0                    0  0  0

The algorithm would incorrectly zero out the entire matrix!

The Solution: Always use a two-pass approach with separate marking arrays to preserve the original zero positions before making any modifications.

Pitfall 2: Space optimization attempt using O(1) space incorrectly

The Problem: Some might try to achieve O(1) space by using the first row and column as markers, but forget to handle them specially:

# INCORRECT O(1) space attempt
for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            matrix[i][0] = 0  # Use first column as row marker
            matrix[0][j] = 0  # Use first row as column marker

# This corrupts the information about whether the first row/column
# themselves originally contained zeros

The Solution: If attempting O(1) space optimization, you must:

1. First check if the first row and column contain any zeros and store this in separate boolean variables
2. Use the first row and column to mark other rows/columns (starting from index 1)
3. Process the matrix from bottom-right to top-left, leaving the first row and column for last
4. Finally, zero out the first row and column based on the initial boolean flags

The O(m+n) space solution with separate arrays is much cleaner and less error-prone, making it the preferred approach unless space is extremely constrained.