Java solution, in place and back tracking.


  • 0
    M

    Easiest way is, on first iteration just store row and column indexes in different lists and then iterate whole matrix again and set zeroes for these indexes.

    public void setZeroes(int[][] matrix){
    		List<Integer> rows = new ArrayList<Integer>();
            List<Integer> columns = new ArrayList<Integer>();
    	for (int i = 0; i < matrix.length; i++) {
    		for (int j = 0; j < matrix[0].length; j++) {
    			if(matrix[i][j]==0)
    				rows.add(i);columns.add(j);
    		}
    	}
    	for (int i = 0; i < matrix.length; i++) {
    		for (int j = 0; j < matrix[0].length; j++) {
    			if(rows.contains(i) || columns.contains(j))
    				matrix[i][j] = 0;
    		}
    	}
    }
    

    Then I thought why shouldn't we utilize this list of indexes for which we will have to set zeroes in the same loop. If you think it is possible as we are just traversing through the matrix in linear way if we have indexes in which we had zero we can use them for next rows and columns ( tricky part is previous rows and columns)

    Example: we have below matrix

    1 2 3 [while iterating over ]
    4 0 6 [the matrix we found ]
    7 8 9 [zero at (1,1) ]
    || so we will have (1,1) saved in our row-colum indexes list
    V
    1 2 3 We can have this by just adding one else if in the existing code.
    4 0 0
    7 0 9

    if(matrix[i][j]==0){
    	rows.add(i);columns.add(j);
    }
    else if(rows.contains(i) || columns.contains(j)){
    	matrix[i][j] = 0;
    }
    

    But what about the indexes which we have traversed already for that we will need two for loops to go back and set zeroes on those indexes. So here comes the final solution.

     public void setZeroes(int[][] matrix) {
        	List<Integer> rows = new ArrayList<Integer>();
            List<Integer> columns = new ArrayList<Integer>();
    	
            for (int i = 0; i < matrix.length; i++) {
    		for (int j = 0; j < matrix[0].length; j++) {
    			if(matrix[i][j]==0){
    				rows.add(i);columns.add(j);
    				for(int k=i-1;k>=0;k--)
    					matrix[k][j] = 0;
    				for(int l=j-1;l>=0;l--)
    					matrix[i][l] = 0;
    			}else if(rows.contains(i) || columns.contains(j))
    	  			matrix[i][j] = 0;
            }
        }
    }
    

    I ll be very happy to hear any improvement/suggestion. Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.