class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Modify the given m x n matrix in-place such that if an element is 0,
its entire row and column are set to 0.
Parameters:
matrix (List[List[int]]): A 2D list of integers representing the matrix.
Operation:
This function uses the first row and first column of the matrix as flags
to record if a row or column should be set to 0, thereby achieving constant
additional space usage.
"""
if not matrix or not matrix[0]:
return # If matrix is empty, no action is needed.
rows, cols = len(matrix), len(matrix[0])
# Check if the first row contains any zeros.
first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
# Check if the first column contains any zeros.
first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
# Use first row and column as markers.
# If a cell matrix[i][j] is 0, set matrix[i][0] and matrix[0][j] to 0.
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][j] == 0:
matrix[i][0] = 0 # Mark the row.
matrix[0][j] = 0 # Mark the column.
# Iterate over the matrix again and using the markers, set elements to 0.
for i in range(1, rows):
for j in range(1, cols):
# If either the row or column is marked, set the element to 0.
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Zero out the first row if needed.
if first_row_zero:
for j in range(cols):
matrix[0][j] = 0
# Zero out the first column if needed.
if first_col_zero:
for i in range(rows):
matrix[i][0] = 0
Summary of Techniques and Approaches:
In-Place Marking: The solution leverages the matrix’s first row and column to mark which rows and columns should be zeroed, eliminating the need for extra space. This pattern is valuable when memory usage must be minimized.
Two-Pass Processing: The algorithm uses an initial pass to set markers and a subsequent pass to update the matrix elements. This strategy of separating detection/marking from processing is broadly applicable to various problems where state needs to be preserved temporarily.
Edge Case Handling: Special handling for the first row and first column ensures that the marker mechanism doesn’t interfere with the final output. Identifying such corner cases is crucial in designing robust in-place algorithms.
Applicability Across Problems: Techniques like in-place modification and using parts of the input data structure as auxiliary storage are common in other scenarios such as partitioning problems, dynamic programming with state reuse, and array manipulation challenges. Recognizing when the input itself can serve dual purposes (data + marker) can lead to both memory and time-efficient solutions.