## DEV Community

sachin26

Posted on • Updated on

# Striver's SDE Sheet Journey - #1 Set Matrix Zeroes

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

my main purpose to start this Journey
- To improve DSA Concepts.
- To improve code Quality.
- To continue learning Journey
- To help to you Guys ๐

## #1 Set Matrix Zeroes

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

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

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

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

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

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

step-5 end

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){

}
}
}

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

Algo #1

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

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

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

3. end

Dry Run

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

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

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

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

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

``````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)

Algo #2

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

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

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

(1.2) set entire column to -11

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

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

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

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

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

at matrix[2][2] loop end.

step-3 end

JAVA CODE

``````
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.