Set Matrix Zeroes

Problem Description

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

You must do it in-place.

Examples

Constraints

• m == matrix.length
• n == matrix[0].length
• 1 ≤ m, n ≤ 200
• -2³¹ ≤ matrix[i][j] ≤ 2³¹ - 1

Using the First Row and Column as In-Place Markers

The naive approach is allocating a separate boolean grid to mark which rows and columns should be zeroed out. This uses O(m * n) space. We can optimize this to O(m + n) space by maintaining two separate 1D arrays: zero_rows and zero_cols.

To achieve O(1) auxiliary space, we can reuse the first row and first column of the matrix itself to act as our tracking arrays.

• Scan the matrix starting from index (1, 1). If matrix[r][c] == 0, we mark its row and column by setting matrix[r][0] = 0 and matrix[0][c] = 0.
• Because cell (0, 0) is shared, we use an extra boolean variable rowZero to track if the first row itself needs to be zeroed out.
• After marking, we scan the inner matrix again and zero out cells based on the markers in the first row and column.
• Finally, we update the first row and column themselves based on their respective state trackers.

Solution 1: First Row/Col Markers (O(1) Space)

Use the matrix borders as state markers, with an extra boolean variable for the first row’s zero state.

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean rowZero = false; // track if the first row needs to be zeroed

        // Step 1: find zeroes and mark them on borders
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[0][c] = 0; // mark column
                    if (r > 0) {
                        matrix[r][0] = 0; // mark row
                    } else {
                        rowZero = true; // mark first row
                    }
                }
            }
        }

        // Step 2: zero out cells based on border markers
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Step 3: zero out the first column if needed
        if (matrix[0][0] == 0) {
            for (int r = 0; r < rows; r++) {
                matrix[r][0] = 0;
            }
        }

        // Step 4: zero out the first row if needed
        if (rowZero) {
            for (int c = 0; c < cols; c++) {
                matrix[0][c] = 0;
            }
        }
    }
}

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        row_zero = False  # track first row state

        # Step 1: find zeroes and mark them on borders
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0  # mark column
                    if r > 0:
                        matrix[r][0] = 0  # mark row
                    else:
                        row_zero = True  # mark first row

        # Step 2: zero out cells based on border markers
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        # Step 3: zero out the first column if needed
        if matrix[0][0] == 0:
            for r in range(rows):
                matrix[r][0] = 0

        # Step 4: zero out the first row if needed
        if row_zero:
            for c in range(cols):
                matrix[0][c] = 0

#include <vector>

class Solution {
public:
    void setZeroes(std::vector<std::vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        bool rowZero = false; // track first row state

        // Step 1: find zeroes and mark them on borders
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[0][c] = 0; // mark column
                    if (r > 0) {
                        matrix[r][0] = 0; // mark row
                    } else {
                        rowZero = true; // mark first row
                    }
                }
            }
        }

        // Step 2: zero out cells based on border markers
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Step 3: zero out the first column if needed
        if (matrix[0][0] == 0) {
            for (int r = 0; r < rows; r++) {
                matrix[r][0] = 0;
            }
        }

        // Step 4: zero out the first row if needed
        if (rowZero) {
            for (int c = 0; c < cols; c++) {
                matrix[0][c] = 0;
            }
        }
    }
};

Complexity Analysis:

• Time Complexity: O(m * n) where m is rows and n is columns. We scan the grid three times.
• Space Complexity: O(1) auxiliary space.

Where it breaks: Nothing breaks for standard integer inputs. If you attempt to update the borders without the rowZero variable (meaning you use matrix[0][0] to track both the first row and column), you will overlap states and end up zeroing out the entire matrix unnecessarily on grids like [[1, 1], [0, 1]].

Common Mistakes

• Using a single variable to represent both first row and first column states. The intersection cell matrix[0][0] is shared. If you set matrix[0][0] = 0 to indicate a zero in the first column, your code will incorrectly zero out the entire first row in step 4. You must use an independent boolean flag rowZero (or colZero) to resolve this.
• Zeroing out the borders first. If you zero out the first row and column in step 1, you lose all the marker information for the inner cells. Borders must be updated last.
• Modifying the loop index offsets. The inner update loop must start at r = 1 and c = 1 to prevent overwriting the border markers prematurely.

Frequently Asked Questions

Why not use a special marker value (like -9999) to mark cells? Because the cell values are in the full 32-bit integer range. Any chosen number (e.g. Integer.MIN_VALUE) could be a valid value in the input matrix, which leads to false positives. The border marker approach has no such dependency.

How does this change if we only need to set rows to zero? If you only zero out rows, you only need to store row indices, which takes O(m) space, or you can mark the first column in-place using O(1) auxiliary space.

What does this problem test in interviews? It tests your capability to optimize space from linear to constant by reusing the input data structure as a state machine.

← All Problems