Set Matrix Zeroes

Problem Statement

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.

Examples

Example 1:

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

Visual:
1 1 1      1 0 1
1 0 1  =>  0 0 0
1 1 1      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]]

Visual:
0 1 2 0      0 0 0 0
3 4 5 2  =>  0 4 5 0
1 3 1 5      0 3 1 0

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

Solution Approaches

This problem has multiple solutions with different space complexities.

Approach 1: O(m + n) Space - Using Sets

Idea: Track which rows and columns need to be zeroed.

public void setZeroes(int[][] matrix) {
    Set<Integer> zeroRows = new HashSet<>();
    Set<Integer> zeroCols = new HashSet<>();

    // Find all zeros
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 0) {
                zeroRows.add(i);
                zeroCols.add(j);
            }
        }
    }

    // Set rows to zero
    for (int row : zeroRows) {
        for (int j = 0; j < matrix[0].length; j++) {
            matrix[row][j] = 0;
        }
    }

    // Set columns to zero
    for (int col : zeroCols) {
        for (int i = 0; i < matrix.length; i++) {
            matrix[i][col] = 0;
        }
    }
}

Time: O(m × n) Space: O(m + n)

This is straightforward but uses extra space.

Approach 2: O(1) Space - Using First Row/Column as Markers ⭐

Key Insight: Use the first row and column as storage to mark which rows/columns need to be zeroed!

Why this works:

• We can use matrix[i][0] to mark if row i should be zero
• We can use matrix[0][j] to mark if column j should be zero
• But first row and column overlap at matrix[0][0], so we need special handling

Algorithm:

1. Check first row and column separately:

   • Use boolean firstRowHasZero to remember if first row has a zero
   • Use boolean firstColHasZero to remember if first column has a zero

2. Use first row/column as markers:

   • Scan matrix (excluding first row/column)
   • If matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0

3. Set zeros based on markers:

   • Scan matrix (excluding first row/column)
   • If matrix[i][0] == 0 OR matrix[0][j] == 0, set matrix[i][j] = 0

4. Handle first column (if needed):

   • If firstColHasZero, set entire first column to 0

5. Handle first row (if needed):

   • If firstRowHasZero, set entire first row to 0

Why process first row/column last? We're using them as markers, so we must process them after using them!

Example Walkthrough

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

Step 1: Check first row/column

• First row [1,1,1] → no zero → firstRowHasZero = false
• First column [1,1,1] → no zero → firstColHasZero = false

Step 2: Use first row/column as markers

• Find zero at [1][1]
• Set matrix[1][0] = 0 (mark row 1)
• Set matrix[0][1] = 0 (mark column 1)
• Matrix becomes: [[1,0,1],[0,0,1],[1,1,1]]

Step 3: Set zeros based on markers

• Row 1 is marked (matrix[1][0] = 0), so set row 1 to zeros: [0,0,0]
• Column 1 is marked (matrix[0][1] = 0), so set column 1 to zeros
• Matrix becomes: [[1,0,1],[0,0,0],[1,0,1]]

Step 4: First column not marked, skip

Step 5: First row not marked, skip

Final: [[1,0,1],[0,0,0],[1,0,1]] ✓

Time & Space Complexity

O(1) Space Approach:

• Time Complexity: O(m × n)

  • Two passes through the matrix

• Space Complexity: O(1)

  • Only using two boolean variables

O(m + n) Space Approach:

• Time Complexity: O(m × n)
• Space Complexity: O(m + n)

Java Solution (O(1) Space)

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;

        // Check if first row has zero
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Check if first column has zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;  // Mark row
                    matrix[0][j] = 0;  // Mark column
                }
            }
        }

        // Set zeros based on markers (excluding first row/col)
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Handle first column
        if (firstColHasZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

        // Handle first row
        if (firstRowHasZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

Python Solution (O(1) Space)

def setZeroes(matrix: List[List[int]]) -> None:
    m, n = len(matrix), len(matrix[0])

    first_row_has_zero = False
    first_col_has_zero = False

    # Check if first row has zero
    for j in range(n):
        if matrix[0][j] == 0:
            first_row_has_zero = True
            break

    # Check if first column has zero
    for i in range(m):
        if matrix[i][0] == 0:
            first_col_has_zero = True
            break

    # Use first row and column as markers
    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

    # Set zeros based on 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

    # Handle first column
    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

    # Handle first row
    if first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0

Related Problems

• Rotate Image (LeetCode 48): In-place matrix rotation
• Spiral Matrix (LeetCode 54): Matrix traversal
• Game of Life (LeetCode 289): Similar in-place modification
• Valid Sudoku (LeetCode 36): Matrix validation
• Toeplitz Matrix (LeetCode 766): Matrix pattern checking

Pattern Recognition

This problem demonstrates:

• In-place algorithm with space optimization
• Matrix manipulation pattern
• Marker/flag technique
• Two-pass algorithm

Common Mistakes

1. ❌ Setting zeros immediately (corrupts data for later cells)
2. ❌ Not handling first row/column specially
3. ❌ Processing first row/column before using them as markers
4. ❌ Wrong order: must set first column before first row (or vice versa with adjustment)
5. ❌ Using matrix[0][0] for both first row and column (creates ambiguity)
6. ❌ Not using firstRowHasZero and firstColHasZero flags

Tips for Interviews

• Start Simple: Mention the O(m+n) space solution first
• Optimize: Then explain the O(1) space approach
• Key Insight: Explain using first row/column as storage
• Order Matters: Emphasize why we process first row/column last
• Draw It: Use a small 3×3 example on the whiteboard
• Edge Cases: Single row, single column, all zeros, no zeros
• Clarify: Confirm it must be in-place before optimizing

Follow-Up Questions

1. Q: What if you can't modify the input?

   • A: Must use O(m + n) space for sets/arrays

2. Q: What if matrix is read-only except for zeros?

   • A: Can't use in-place approach, need extra space

3. Q: Can you do it in one pass?

   • A: No, you need at least two passes (scan then modify)

4. Q: What if matrix is very large (doesn't fit in memory)?

   • A: Process in chunks/blocks, but complex to implement

Complexity Comparison

| Approach | Time | Space | Notes | |----------|------|-------|-------| | Naive (create new matrix) | O(m×n) | O(m×n) | Simple but wasteful | | Sets for rows/cols | O(m×n) | O(m+n) | Clean and intuitive | | First row/col markers | O(m×n) | O(1) | Optimal ⭐ |

Why O(1) Space is Tricky

The challenge is that we're using part of the input as auxiliary storage:

• First row stores "which columns need zeroing"
• First column stores "which rows need zeroing"
• But they might originally contain zeros themselves!
• Solution: Remember their original state in boolean flags

This is a classic space optimization technique!

Visual Example

For [[0,1,2,0],[3,4,5,2],[1,3,1,5]]:

Step 1: Original + Check first row/col
0 1 2 0  → firstRowHasZero = true
3 4 5 2
1 3 1 5

Step 2: Mark using first row/col
0 1 2 0  → Found 0 at [0][0], already in first row
3 4 5 2  → Mark [0][3] = already 0
1 3 1 5  → No changes needed

Step 3: Set zeros (excluding first row/col)
0 1 2 0
0 4 5 0  → Set based on markers
0 3 1 0  → Set based on markers

Step 4: Set first column (firstColHasZero = true)
0 1 2 0
0 4 5 0
0 3 1 0

Step 5: Set first row (firstRowHasZero = true)
0 0 0 0  → Final result
0 4 5 0
0 3 1 0