Set Matrix Zeroes Leetcode Solution

Difficulty Level Medium
Array HashMap Juspay MatrixViews 36

Problem Statement

The Set Matrix Zeroes LeetCode Solution – “Set Matrix Zeroes” states that you’re given an `m x n` integer matrix `matrix`.We need to modify the input matrix such that if any cell contains the element  `0`, then set its entire row and column to `0`‘s.

You must do it in place.

Example:

`Input:  matrix = [[1,1,1],[1,0,1],[1,1,1]]`
`Output: [[1,0,1],[0,0,0],[1,0,1]]`

Explanation:

• The above matrix contains the zero at position (1,1).
• Hence, we need to make the entire 1st row as well as the 1st column zero.
`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 above matrix contains zero’s at positions (0,0) and (0,3).
• Hence, we need to make the entire 0th row,0th column, and 3rd column zero.

Approach

Idea:

1. The main idea to solve this problem efficiently in O(1) extra space is to use the `0th` row and `0th`column to track which rows and columns will be marked with all zeroes.
2. `matrix[i][0]==0`will denote that the entire `ith` the row should be marked with `0`‘s.
3. `matrix[0][j]==0`will denote that the entire `jth` the column should be marked with `0`‘s.
4. First iterate in the `0th`row and`0th`column and check whether there exists a zero. Store the results in the boolean variable `f1` and `f2`.
5. Now, iterate in the remaining rows and columns and mark the respective `matrix[i][0]`and `matrix[0][j]`if `(i,j)`cell contains `0`.
6. Now, we need to modify the input matrix.
7. Iterate for all the rows and columns except `0th` row and `0th`column and set `0` if required using the data from `matrix[i][0]`and `matrix[0][j]`.
8. Finally, use boolean variables `f1` and `f2` to mark `0th` row and `0th`column.

Code

Set Matrix Zeroes Leetcode C++ Solution:

```class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool f1 = false,f2 = false;
int n = matrix.size(),m = matrix.back().size();
for(int i=0;i<n;i++){
if(matrix[i][0]==0){
f1 = true;
}
}
for(int j=0;j<m;j++){
if(matrix[0][j]==0){
f2 = true;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(matrix[i][j]==0){
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(matrix[i][0]==0 || matrix[0][j]==0){
matrix[i][j] = 0;
}
}
}
if(f1){
for(int i=0;i<n;i++){
matrix[i][0] = 0;
}
}
if(f2){
for(int j=0;j<m;j++){
matrix[0][j] = 0;
}
}
}
};```

Set Matrix Zeroes Leetcode Java Solution:

```class Solution {
public void setZeroes(int[][] matrix) {
boolean f1 = false,f2 = false;
int n = matrix.length,m = matrix[0].length;
for(int i=0;i<n;i++){
if(matrix[i][0]==0){
f1 = true;
}
}
for(int j=0;j<m;j++){
if(matrix[0][j]==0){
f2 = true;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(matrix[i][j]==0){
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(matrix[i][0]==0 || matrix[0][j]==0){
matrix[i][j] = 0;
}
}
}
if(f1){
for(int i=0;i<n;i++){
matrix[i][0] = 0;
}
}
if(f2){
for(int j=0;j<m;j++){
matrix[0][j] = 0;
}
}
}
}```

Complexity Analysis for Set Matrix Zeroes Leetcode Solution

Time Complexity

The time complexity of the above code is O(M*N) where M = number of rows of matrix and N = number of columns of the matrix.

Space Complexity

The space complexity of the above code is O(1) since we aren’t using any extra space.

Translate »