This content originally appeared on DEV Community and was authored by sachin26
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 my DSA Concepts.
- To improve my code Quality.
- To continue my learning Journey
- To Help to you Guys 😊
let's start with 1st problem.
#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) which 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){
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
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
check if isFirstRowHas0 is true then set 1stRow to 0's
check if isFirstColHas0 is true then set 1stCol to 0's
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
-
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 again traverse the matrix and replace all -11 to 0
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;
}
}
}
}
for(int row=0;row<rows;row++){
for(int col =0;col<cols;col++){
// replace dummyInt to 0
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 post or maybe not 😔.please share your words in the comment section.
thanks for reading my first post.
This content originally appeared on DEV Community and was authored by sachin26
sachin26 | Sciencx (2021-12-11T08:42:48+00:00) Striver’s SDE Sheet Journey #1 Set Matrix Zeroes. Retrieved from https://www.scien.cx/2021/12/11/strivers-sde-sheet-journey-1-set-matrix-zeroes/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.