73. Set Matrix Zeroes - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given an m x n matrix, if an element is 0, set its entire row and column to 0. You must do this 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]
]

Explanation:
The element at (1,1) is 0, so its entire row and column are set to 0.

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

Explanation:
The first row has zeros at positions (0,0) and (0,3), so row 0 and columns 0 and 3 become zeros.

Constraints:

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

Hints

Hint 1:
Think about first identifying all the rows and columns that need to be set to zero. A straightforward method is to use two additional arrays (or sets) to store the indices of rows and columns with at least one zero.
Hint 2:
To achieve constant extra space, consider using the first row and first column of the matrix as markers for whether a particular row or column should be set to zero. However, you need to handle the first row and first column separately since they serve as both data and markers.
Hint 3:
When updating the matrix based on the markers, be sure to avoid early modifications that may affect the marker values. Process the matrix in multiple passes: first, mark the rows and columns, then update the matrix accordingly.

Approaches

Approach 1: Using Additional Memory (Brute Force Variation)

Idea:
Create two extra arrays (or sets) to record the row indices and column indices where a zero occurs. Then iterate over the matrix again and update cells to zero if their row or column index is recorded.
Drawbacks:
Requires O(m + n) extra space, which is acceptable but not optimal if constant space is desired.

Approach 2: Optimal Constant Space Solution

Idea:
Use the first row and first column of the matrix as markers:
1. Marker Phase:
  - Traverse the matrix. If an element is 0, mark its corresponding row and column by setting the first element of that row and first element of that column to 0.
  - Use separate flags to track whether the first row and first column originally had any zero.
2. Update Phase:
  - Iterate over the matrix (excluding the first row and column) and set cell to 0 if the marker in its row or column is 0.
3. Final Phase:
  - Update the first row and first column based on the flags.
Benefits:
This approach uses O(1) extra space (ignoring the input) and processes the matrix in multiple passes, making it efficient and optimal.

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
The solution involves multiple passes over the matrix (to mark and then update), each taking O(m * n) time.

Overall: O(m * n).
Space Complexity:
Using constant extra space (only a few boolean flags), the solution is O(1) aside from the input matrix.

Step-by-Step Walkthrough

Marker Initialization:
- Check if the first row or first column contains any zeros and save these results in two boolean variables (firstRowZero and firstColZero).
Marking Phase:
- For every cell (excluding the first row and first column), if the cell is 0, mark its row and column by setting the first element of that row and the first element of that column to 0.
Update Phase:
- For each cell (again, excluding the first row and first column), if its corresponding marker in the first row or column is 0, set that cell to 0.
Final Update:
- If firstRowZero is true, set all elements in the first row to 0.
- If firstColZero is true, set all elements in the first column to 0.
Result:
- The matrix is updated in place with rows and columns set to 0 according to the problem statement.

Visual Example

Consider the matrix:

[
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]

Marker Phase:
The cell (1,1) is 0. Mark row 1 and column 1 by setting matrix[1][0] and matrix[0][1] to 0.

Matrix becomes:
```
[
  [1, 0, 1],
  [0, 0, 1],
  [1, 1, 1]
]
```
Update Phase:
For cells (1,2) and (2,1), since their markers indicate zero in their row or column, update them accordingly.
Final Update:
Since the first row and first column were not originally marked with zero, they remain unchanged except for the marker positions.

Final Matrix:

[
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]

Common Mistakes

Overwriting Markers Too Early:
Updating the matrix in one pass without using markers may result in overwriting data needed for further decisions.
Not Handling First Row/Column Separately:
Failing to check and update the first row and first column independently can lead to incorrect results.
Using Extra Space Unnecessarily:
While extra arrays can solve the problem, they don’t meet the optimal constant space requirement.

Edge Cases

Matrix with No Zeroes:
The matrix should remain unchanged.
Matrix Where Entire Row/Column is Zero:
Ensure that rows or columns already filled with zeros are handled correctly.
Single Row or Single Column:
The solution should correctly update matrices with one row or one column.

Zero Matrix:
Problems where you need to propagate a property (like zero) across a grid.
Matrix Diagonal or Border Updates:
Similar in-place update techniques may be required for other matrix manipulation problems.

Flood Fill
Game of Life
Rotate Image
Spiral Matrix