Striver's SDE Sheet Journey - #1 Set Matrix Zeroes
Tags: beginners, programming, java, dsa
Published: 2021-12-11 08:42:48

Hi👋,devs.

from today I have decided I am going to start a journey called **_Striver's SDE Sheet Journey_** and in this journey, I will solve all 180 problems and I will try to explain all the solutions in an understandable way or I should say that step by step so that you can easily understand the solutions.
Throughout the journey, I will use java, why java? because I feel comfortable with it.

 What is "**Striver's SDE Sheet**" 🤔? [👀 here](https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/)

**my main purpose to start this Journey**
_- To improve DSA Concepts._
_- To improve code Quality._
_- To continue learning Journey_ 
_- To help to you Guys 😊_


---


let's start with 1st problem.

## <u>**#1 Set Matrix Zeroes**</u>

In this problem, we have given a 2D integer matrix and in this matrix if an element is 0 then we have to set its entire **ROW** and **COLUMN** to 0's.

 _like this one_
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0rmoxgnr58070muy7c76.jpeg)

> _**my approach**_

_after spending half an hour I got this approach. let's discuss step by step_

**1.** create two integer arrays(zeroRowIndexList & zeroColIndexList) ,that store the index of row and column.

**2.** traverse the matrix and add the index of row & column to the arrays(zeroRowIndexList & zeroColIndexList) if **matrix[row][column] == 0**.

**3.** set matrix's entire row to 0's according to zeroRowIndexList array.

**4.** set matrix's entire column to 0's according to zeroColIndexList array.

**5.** end

let's Dry run this approach with an example

```javascript
matrix = [[1,1,1],[1,0,1],[1,1,1]]
```

 **step-1** create two arrays `zeroRowIndexList=[ ]`,`zeroColIndexList=[ ]`.


 **step-2** traverse the matrix and add index of row & column to the arrays(zeroRowIndexList,zeroColIndexList) if **matrix[row][col] == 0**
 >>       at matrix[0,0] == 0 is false
 >>       at matrix[0,1] == 0 is false
 >>       .
 >>       .
 >>       at matrix[1,1] == 0 is true 
 >>       then add index of row & col to the arrays e.g. zeroRowIndexList=[1],zeroColIndexList=[1]
 >>       at matrix[1,2] == 0 is false
 >>       at matrix[2,2] == 0 is false


 **step-3** from `zeroRowIndexList[1]` array, set matrix's rows to 0's
       

```javascript
 matrix = [[1,1,1],[0,0,0],[1,1,1]]
```


 **step-4** from `zeroColIndexList[1]` array, set matrix's columns to 0's
        

```javascript
matrix = [[1,0,1],[0,0,0],[1,0,1]]
```


 **step-5** end

 

>   **_JAVA_**

```java
import java.util.ArrayList;
class Solution {
    
    public void setZeroes(int[][] matrix) {
         ArrayList<Integer> zeroRowIndexList = new ArrayList<Integer>();
         ArrayList<Integer> zeroColIndexList = new ArrayList<Integer>();
         int rows = matrix.length;
         int cols = matrix[0].length;
        
        // traverse the matrix and add row index & col index to Arraylists,
        // if cell element == 0
         for(int row =0 ;rows > row;row++){
             for(int col =0 ;cols> col;col++){
                 if(matrix[row][col] == 0){
                 zeroRowIndexList.add(row);
                 zeroColIndexList.add(col);
    
                 }
             }
         }
        
        // set entire row & col to 0 
        for(int index =0 ;zeroColIndexList.size() > index;index++ ){
          setRowZeros(matrix,zeroRowIndexList.get(index));
          setColumnZeros(matrix,zeroColIndexList.get(index));
        }
       
    }
    
    // set entire row to 0
    void setRowZeros(int[][] matrix,int rowIndex){
        int size = matrix[rowIndex].length;
        matrix[rowIndex] = new int[size];
    }
    
    // set entire column to 0
    void setColumnZeros(int[][] matrix,int colIndex){
        int rows = matrix.length;
        for(int row =0;row<rows; row++){
           matrix[row][colIndex] = 0;
        }
    }
    
}
```

> **_Complexity Analysis_**

_Time Complexity_ :- **O(rows*cols)**
_Space Complexity_ :- **O(rows+cols)**



> _**other approaches**_

 <u>**Algo #1**</u>

_instead of creating two separate arrays we can use the matrix's first row & first column as markers._ 
let's see how

**1.** create two boolean variable called **isFirstRowHas0** and **isFirstColHas0** and set to false

**2.** traverse the matrix and 

>> (2.1) if matrix[row][col] == 0 then 

> >> (3.1) if row == firstRow then set isFirstRowHas0 to true
> >> (3.2) if col == firstCol then set isFirstColHas0 to true
> >> (3.3) mark corresponding 1st row & 1st column to 0 
     e.g. matrix[firstRow][col] == 0 & matrix[row][firstCol] == 0

**3.** again traverse the matrix from matrix[2ndRow][2ndCol] and set 0 if matrix[firstRow][col] == 0 or matrix[row][firstCol] == 0

4. check if isFirstRowHas0 is true then set 1stRow to 0's

5. check if isFirstColHas0 is true then set 1stCol to 0's

6. end

> **Dry Run**

```javascript
matrix = [[1,1,1],[1,0,1],[1,1,1]]
```

**step-1** initialised two boolean variable isFirstRowHas0,isFirstColHas0 and set to false
>>  `isFirstRowHas0 = false`
>>  `isFirstColHas0 = false`

**step-2** traverse the matrix till the end
>> (2.1) at matrix[0,0] == 0 is false
>> ..
>> (2.1) at matrix[1,1] == 0 is true then
> >> (3.1) if 1 == 0 is false 
> >> (3.2) if 1 == 0 is false 
> >> (3.3) matrix[firstRow][1] = 0 & matrix[1][firstCol] = 0
```javascript
matrix = [[1,0,1],[0,0,1],[1,1,1]]
```
>> ..
>> (2.1) at matrix[2,2] loop end

**step-3** again traverse the matrix from matrix[2ndRow][2ndCol]
>> at matrix[1,1] if matrix[firstRow][1] == 0 or matrix[row][firstCol] == 0 is true then set matrix[1,1] = 0
```javascript
matrix = [[1,0,1],[0,0,1],[1,1,1]]
```
>> at matrix[1,2] if matrix[firstRow][2] == 0 or matrix[1][firstCol] == 0 is true then set matrix[1,2] = 0
```javascript
matrix = [[1,0,1],[0,0,0],[1,1,1]]
```
>> at matrix[2,1] if matrix[firstRow][1] == 0 or matrix[row][firstCol] == 0 is true then set matrix[2,1] = 0
```javascript
matrix = [[1,0,1],[0,0,0],[1,0,1]]
```
>> at matrix[2,2] if matrix[firstRow][1] == 0 or matrix[row][firstCol] == 0 is false 

**step-4** if `firstRowHas0 == true` is false

**step-5** if `firstColHas0 == true` is false

**step-6** end


> **_JAVA_**
```java
class Solution {
    
    public void setZeroes(int[][] matrix){
      
      int rows = matrix.length;
      int cols = matrix[0].length;
      int firstRow = 0;
      int firstCol = 0;
      boolean isFirstColHas0 = false;
      boolean isFirstRowHas0 = false;
      
      for(int row =0; row  < rows; row++){
          
          for (int col = 0; col < cols; col++) {
           
              if(matrix[row][col] == 0){
                      
              if(col == firstCol) isFirstColHas0 = true;
              if(row == firstRow)  isFirstRowHas0 = true;
                  
              matrix[firstRow][col] = matrix[row][firstCol] = 0;
       
              }      
          }
      }

      for (int row = 1; row < rows; row++) {
        for(int col =1; col < cols;col++){
            if(matrix[row][firstCol] ==0 || matrix[firstRow][col] ==0){
                matrix[row][col] =0;
            }
        }
          
      }

      if(isFirstColHas0){
          setFirstColumnZeros(matrix,firstCol);
      }
      if(isFirstRowHas0){
          setFirstRowZeros(matrix,firstRow);
      }
    }
    
    // set 1st entire row to 0
    void setFirstRowZeros(int[][] matrix,int rowIndex){
        matrix[rowIndex] = new int[matrix[rowIndex].length];
    }
    
    // set 1st entire column to 0
    void setFirstColumnZeros(int[][] matrix,int colIndex){
        for(int rowIndex =0;matrix.length > rowIndex; rowIndex++){
           matrix[rowIndex][colIndex] = 0;
        }
    }
    
}
```

> **_Complexity Analysis_**

_Time Complexity_ :- **O(rows*cols)**
_Space Complexity_ :- **O(1)**


<u> **Algo #2**</u>

_in this approach, i assume that **-11** will not occur in the matrix_

1. traverse the matrix and if matrix[row][col] == 0 then set entire row & col to -11 if **matrix[row][col] != 0**
>> (1.1) set entire row to -11 if matrix[row][col] != 0
>> (1.2) set entire column to -11 if matrix[row][col] != 0

2. again traverse the matrix and replace all -11 to 0

3. end

> **_Dry Run_**

```javascript
matrix = [[1,1,1],[1,0,1],[1,1,1]]
```

**step-1** traverse the matrix

 > at matrix[0][0] if matrix[0][0] == 0 is false
 > ..
 > at matrix[1][1] if matrix[1][1] == 0 is true then
 >>  (1.1) set entire row to -11 if matrix[1][col] != 0


```javascript
matrix = [[1,1,1],[-11,0,-11],[1,1,1]]
```
 >>  (1.2) set entire column to -11

```javascript
matrix = [[1,-11,1],[-11,0,-11],[1,-11,1]]
```

>  ..
>  at matrix[2][2] loop end


**step-3** again traverse the matrix 
> at matrix[0][0] == -11 is false
> at matrix[0][1] == -11 is true then replace the value to 0

```javascript
matrix = [[1,0,1],[-11,0,-11],[1,-11,1]]
```

> at matrix[0][2] == -11 is false
> at matrix[1][0] == -11 is true then replace the value to 0

```javascript
matrix = [[1,0,1],[0,0,-11],[1,-11,1]]
```
> at matrix[1][1] == -11 is false

> at matrix[1][2] == -11 is true then replace the value to 0

```javascript
matrix = [[1,0,1],[0,0,0],[1,-11,1]]
```
> at matrix[2][0] == -11 is false
> at matrix[2][1] == -11 is true then replace the value to 0

```javascript
matrix = [[1,0,1],[0,0,0],[1,0,1]]
```
> at matrix[2][2] loop end.

**step-3** end

>  _JAVA CODE_

```java

class Solution {
    public void setZeroes(int[][] matrix) {
        int dummyInt = -11;
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // traverse the matrix till the end & set dummyInt to the entire row and column,
        // if the element == 0
        for(int row=0;row<rows;row++){
            for(int col=0;col<cols;col++){
                if(matrix[row][col] == 0){
                    
                    // set -11 to entire column
                    for(int i=0;i<rows;i++){
                        if(matrix[i][col] != 0)
                            matrix[i][col] = dummyInt;
                    }
                    
                    // set -11 to entire row
                    for(int i=0;i<cols;i++){
                        if(matrix[row][i] != 0)
                            matrix[row][i] = dummyInt;
                    }
                }
            }
        }
        
      // again traverse the matrix & replace dummyInt to 0
        for(int row=0;row<rows;row++){
            for(int col =0;col<cols;col++){
               
                if(matrix[row][col] == dummyInt)
                    matrix[row][col] = 0;
            }
        }
        
    }
}

```
> **_Complexity Analysis_**

_Time Complexity_ :- **O(rows*cols)**
_Space Complexity_ :- **O(1)**

---


if you reading this line it means you love 🥳 the article.please share your words in the comment section.
Thank you for reading my first blog.