DEV Community

Cover image for Striver's SDE Sheet Journey - #1 Set Matrix Zeroes
sachin26
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 ๐Ÿ˜Š


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) ,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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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

matrix = [[1,0,1],[0,0,0],[1,0,1]]
Enter fullscreen mode Exit fullscreen mode

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;
        }
    }

}
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

..
(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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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;
        }
    }

}
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

(1.2) set entire column to -11

matrix = [[1,-11,1],[-11,0,-11],[1,-11,1]]
Enter fullscreen mode Exit fullscreen mode

..
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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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;
            }
        }

    }
}

Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)