Tuesday, December 9, 2014

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0. [Coding Question][Java]

Q. Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

Source:


public class Code {
    
    public static void deleteZeros(int[][] a){
        boolean rows[] = new boolean[a.length];
        boolean columns[] = new boolean[a[0].length];
         
        for(int i = 0;i<a.length;++i){
            for(int j = 0;j<a[0].length;++j){
                if(a[i][j]==0){rows[i] = true;columns[j] = true;}
            }
        }
         
        for(int i=0;i<rows.length;++i){
            if(rows[i])
                for(int j=0;j<columns.length;++j)a[i][j]=0;
        }
        for(int j=0;j<columns.length;++j){
            if(columns[j])
                for(int i=0;i<rows.length;++i)a[i][j]=0;
        }
    }
    
    public static void print(int[][] a){
        System.out.println();
        for(int i= 0;i<a.length;++i){
            for(int j = 0;j<a[0].length;++j){
                System.out.print(a[i][j]+" ");
            } 
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args){
       int[][] a=  {
           {1,2,9,2,4},
           {2,0,3,2,1},
           {2,3,4,5,0},
           {3,4,6,3,4}
       };
       deleteZeros(a);
       print(a);
    }
}

Output:

1 0 9 2 0
0 0 0 0 0
0 0 0 0 0
3 0 6 3 0

1 comment:

  1. space (1) solution:
    http://www.geeksforgeeks.org/a-boolean-matrix-question/

    ReplyDelete