Set Matrix Zeroes
Given a 2D integer matrix, if an element is 0, set its entire row and column to 0s. You must do this in-place, meaning you should modify the original matrix. This is a common problem that tests your understanding of how to manage state within a data structure and optimize for space complexity.
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, its entire row and its entire column are set to 0.
Key Requirements:
- Modify the matrix in-place.
- The original matrix structure (dimensions) should be preserved.
Expected Behavior:
When a 0 is encountered at matrix[i][j], all elements in the i-th row and all elements in the j-th column should become 0.
Edge Cases:
- An empty matrix.
- A matrix with only one row or one column.
- A matrix where all elements are already 0.
- A matrix with no 0s.
Examples
Example 1:
Input:
[
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
Output:
[
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
Explanation:
The element at `matrix[1][1]` is 0. Therefore, the entire row 1 and column 1 are set to 0s.
Example 2:
Input:
[
[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]
]
Explanation:
The elements at `matrix[0][0]` and `matrix[0][3]` are 0.
Row 0 should be all 0s.
Column 0 should be all 0s.
Column 3 should be all 0s.
Example 3:
Input:
[
[1, 2, 3],
[4, 5, 6]
]
Output:
[
[1, 2, 3],
[4, 5, 6]
]
Explanation:
There are no 0s in the matrix, so no changes are made.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1- The solution should aim for optimal space complexity, ideally O(1) extra space.
Notes
Consider how you can mark rows and columns that need to be zeroed out without using significant extra memory. Think about what parts of the matrix itself can be repurposed to store this information. Avoid naive solutions that might use O(m*n) or O(m+n) extra space if an O(1) solution is achievable.