58. Set Matrix Zeroes

Topic :

matrix

Difficulty :

medium

Problem Link :

link

problem statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

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

Example 2:

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

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

solution

APPROACH 1: USING DUMMY ARRAYS

import java.io.*;
import java.util.*;
class SetMatrix_Zero_Using_Dummy_Arrays
{

static void setZeroes(int a[][])
{
    int row[]=new int[a.length];
    int col[]=new int [a[0].length];
    for(int i=0;i<row.length;i++)
    row[i]=-1;
    for(int i=0;i<col.length;i++)
    col[i]=-1;
        
    for(int i=0;i<a.length;i++)
    { for(int j=0;j<a[0].length;j++)
        { if(a[i][j]==0)
            { row[i]=0;
                col[j]=0;
            }
        }
    }
    
    for(int i=0;i<a.length;i++)
    { for(int j=0;j<a[0].length;j++)
        { if(row[i]==0 || col[j]==0)
            { 
                a[i][j]=0;
            }
        }
    }
}
public static void main(String args[])
     { int matrix[][]={{1,1,1},
                       {1,0,1},
                       {1,1,1}
                       };
        setZeroes(matrix);
        for(int i=0;i<matrix.length;i++)
        {
            for (int j=0;j<matrix[0].length;j++)
           { System.out.print(matrix[i][j]+" "); 
            }
            System.out.println();
     }
    }
}

APPROACH 2: SPACE OPTIMIZED

import java.io.*;
import java.util.*;
public class SetMatrix_Zero_Space_Optimized
{
    public static void main(String args[])
    {
      int matrix[][]={{1,1,1},{1,0,1},{1,1,1}};
      setZeroes(matrix);
      
      for(int i=0;i<matrix.length;i++)
      { for(int j=0;j<matrix[0].length;j++)
          { System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void setZeroes(int[][] matrix) {
        int rows=matrix.length;
        int cols=matrix[0].length;
        boolean col0=true;
        
        // while filing dummy arrays//
        for (int i=0;i<rows;i++)
        {
            if(matrix[i][0]==0)
                col0=false;
            for(int j=1;j<cols;j++)
            {
                if(matrix[i][j]==0)
                    matrix[i][0]=matrix[0][j]=0; // 0th row and 0th col as the dummy arrays
            }
        }
        
        
        // while filling the 2d matrix//
        
        for(int i=rows-1;i>=0;i--)
        {
            for(int j=cols-1;j>=1;j--)
            { if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
            }
            if(col0==false)
                matrix[i][0]=0; // make the first col to be 0
        }
        
    }
}