Set Matrix Zeroes

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]]

Constraints:

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

Follow up:

A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution

Approach 1: O(1) Space - Use First Row and Column as Markers

The key insight is to use the first row and first column to store information about which rows and columns should be zeroed.

Implementation

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        first_row_zero = False
        first_col_zero = False

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

        # Check if first column should be zero
        for i in range(m):
            if matrix[i][0] == 0:
                first_col_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

        # Zero out cells 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 row
        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0

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

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

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_rows = set()
        zero_cols = set()

        # Find all rows and columns that should be zero
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zero_rows.add(i)
                    zero_cols.add(j)

        # Set rows to zero
        for i in zero_rows:
            for j in range(n):
                matrix[i][j] = 0

        # Set columns to zero
        for j in zero_cols:
            for i in range(m):
                matrix[i][j] = 0

Approach 3: O(1) Space - Compact Version

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_col_zero = False

        # Use first column to mark rows, check if first column itself needs zeroing
        for i in range(m):
            if matrix[i][0] == 0:
                first_col_zero = True
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # Zero out cells based on markers (process backwards to avoid conflicts)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, 0, -1):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
            if first_col_zero:
                matrix[i][0] = 0

Complexity Analysis

O(1) Space Approach:

Time Complexity: O(m × n), we traverse the matrix multiple times.
Space Complexity: O(1), only using constant extra space.

O(m + n) Space Approach:

Time Complexity: O(m × n)
Space Complexity: O(m + n) for the sets.

Key Insights

In-Place Storage: Use the first row and column as storage for marking which rows/columns need to be zeroed.
Separate Flags: Need separate flags for first row and first column since they overlap at matrix[0][0].
Processing Order: Process the matrix from bottom-right to avoid overwriting markers before using them.
Two-Pass Solution: First pass marks, second pass applies the zeros.
Edge Case Handling: Must handle first row and first column specially since they’re used as markers.
Space-Time Tradeoff: O(m + n) space solution is simpler but uses extra space; O(1) solution is more complex but optimal.
Marker Values: We can use the first row/column as markers because if they need to be zero, we track that separately.