Set Matrix Zeroes
Problem Description
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:
Example 2:
Constraints:
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -231 <= matrix[i][j] <= 231 - 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?
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force method involves identifying which rows and columns should be set to zero by iterating over the matrix. We first create a copy of the matrix. Using this copy, we iterate over the entire original matrix. If an element is zero, we set all the elements in the corresponding row and column in the copied matrix to zero. After processing, the original matrix is updated to match the copied matrix.
Steps:
- Create a copy of the original matrix.
- Iterate over each element. If an element is 0, mark the entire row and column in the copied matrix as 0.
- Finally, copy the values from the new matrix to the original matrix.
Code:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
- Space Complexity: O(m * n), due to the additional matrix copy.
2. Using Additional Arrays
Intuition:
Instead of using a complete matrix to keep track of which rows and columns need to be zeroed, we can use two separate arrays. One for rows and another for columns that need to be zeroed. This makes the algorithm more space efficient.
Steps:
- Use two arrays
zeroRowsandzeroColsto track rows and columns with zeroes. - First, iterate through the original matrix to fill
zeroRowsandzeroCols. - Iterate again through the matrix, using
zeroRowsandzeroColsto set the appropriate rows and columns to zero.
Code:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
- Space Complexity: O(m + n) for the row and column arrays.
3. In-Place
Intuition:
To achieve O(1) additional space complexity, we can use the input matrix itself to store the required information. We mark the first cell of the respective row and column as zero if we encounter a zero during our matrix traversal. We should be careful while marking to save the state of the first row and column initially because they will be modified during the marking process.
Steps:
- Determine if the first row and first column need to be zeroed for later reference.
- Use the first row and first column to mark whether a row or column should be zero.
- Iterate over the matrix starting from
[1][1], and use the markers in the first row and column to set zeroes. - Finally, handle zeroing of the first row and column based on the stored state in step 1.
Code:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
- Space Complexity: O(1), utilizing the matrix itself for storage.