Skip to content

Instantly share code, notes, and snippets.

@sdpatil

sdpatil/SetZeros.java

Created August 22, 2017 00:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sdpatil/686ec4308dc7814b34f711b48fac1afd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sdpatil/686ec4308dc7814b34f711b48fac1afd to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sdpatil created this gist Aug 22, 2017.
    32 changes: 32 additions & 0 deletions SetZeros.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,32 @@
    /**
    * Problem :- Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
    */
    public class SetZeros {
    /*
    Solution :- First create a boolean matrix for number of rows and another for number of columns
    Then iterate through the matrix if you find zero mark that row and column to zero in boolean matrix
    At the end of first iteration we have marked all the rows or columns that should be marked to zero.
    Now go throug the matrix one more time checking if either the current row or column is marked zero in boolean
    matrix if yes mark that value to zero
    */
    public void setZeros(int[][] matrix) {
    boolean[] zeroRow = new boolean[matrix.length];
    boolean[] zeroColumn = new boolean[matrix[0].length];
    for (int i = 0 ; i < matrix.length ;i++){
    for(int j = 0 ; j < matrix[0].length ; j++){
    if(matrix[i][j] == 0){
    zeroRow[i] = true;
    zeroColumn[j] = true;
    }
    }
    }
    for (int i = 0 ; i < matrix.length ;i++){
    for(int j = 0 ; j < matrix[0].length ; j++){
    if(zeroRow[i] || zeroColumn[j]){
    matrix[i][j] =0;
    }
    }
    }
    }
    }