My O(1) space JAVA solution


  • 0
    Q

    First we need to find if matrix has non-zero row and column. If not we zero out matrix and return

    0 0 1 0 1

    1 2 1 0 2

    1 2 3 4 7

    1 3 5 0 1

    1 4 3 8 9

    Here we find row=2 and column =2 are non zero. And zero out everything above and to the left from the intersection of column and row

    0 0 0 0 1

    0 0 0 0 2

    0 0 3 4 7

    1 3 5 0 1

    1 4 3 8 9

    Next we keep going right looking for column that don't have 0. If the column has zeros we zero out it from row index = 0 to current row (n = 2). O therwise we zero it out from index = 0 to n-1

    0 0 0 0 0

    0 0 0 0 0

    0 0 3 0 7

    1 3 5 0 1

    1 4 3 8 9

    Finally we iterate over remaining rows. If row has 0's we zero it out, otherwise we only keep value if the row's column has a non zero in any position above.

    0 0 0 0 0

    0 0 0 0 0

    0 0 3 0 7

    0 0 0 0 0

    0 0 3 0 9

     public class Solution {
            public void setZeroes(int[][] matrix) {
            	int nonZeroRow = findNonZeroRow(matrix, 0);
                int nonZeroColumn = findNonZeroColumn(matrix, 0);
            	if (nonZeroColumn == -1 || nonZeroRow == -1){
            		zeroOutMatrix(matrix);
            		return;
            	}
            	
            	for (int i=0;i<=nonZeroRow;i++){
            		for (int j=0;j<=nonZeroColumn;j++){
            		    if (! (i==nonZeroRow && j == nonZeroColumn)){
            			    matrix[i][j] = 0;
            		    }
            		}
            	}
            	
            	for (int j=nonZeroColumn+1;j<matrix[0].length;j++){
            		if (isNonZeroColumn(matrix, j)){
            			for (int i=0;i<nonZeroRow;i++){
                			matrix[i][j]=0;
                		}
            		}
            		else{
            			for (int i=0;i<=nonZeroRow;i++){
                			matrix[i][j]=0;
                		}
            		}
            	}
            	
            	for (int i=nonZeroRow+1;i<matrix.length;i++){
            		if (isNonZeroRow(matrix, i)){
            			for (int j=0;j<matrix[0].length;j++){
            				if (!columnHasNonZerosAbove(matrix, j, i)){
            					matrix[i][j] = 0;
            				}
            			}
            		}
            		else {
            			for (int j=0;j<matrix[0].length;j++){
            				matrix[i][j] = 0;
            			}
            		}
            	}
        	}
           
            private boolean columnHasNonZerosAbove(int[][]matrix, int column, int row){
            	for (int i=row-1;i>=0;i--){
            		if (matrix[i][column] != 0){
            			return true;
            		}
            	}
            	return false;
            }
            private int findNonZeroColumn(int[][] matrix, int startColumn){	
        		for (int j=startColumn;j<matrix[0].length;j++){
        			if (isNonZeroColumn(matrix, j)){
        				return j;
        			}
        		}
        		
            	return -1;
            }
            private int findNonZeroRow(int[][] matrix, int startRow){
            	for (int i=startRow;i<matrix.length;i++){
            		if (isNonZeroRow(matrix, i)){
            			return i;
            		}
            	}
            	return -1;
            }
            private boolean isNonZeroColumn(int[][] matrix, int columnIndex){
                for (int i=0;i<matrix.length;i++){
        			if (matrix[i][columnIndex] == 0){
        			    return false;
        			}
        		}
        		return true;
            }
            private boolean isNonZeroRow(int[][] matrix, int rowIndex){
            	for (int j=0;j<matrix[0].length;j++){
        			if (matrix[rowIndex][j] == 0){
        				return false;
        			}
        		}
        		return true;
            }
            private void zeroOutMatrix(int[][] matrix){
            	for (int i=0;i<matrix.length;i++){
            		for (int j=0;j<matrix[0].length;j++){
            			matrix[i][j]=0;
            		}
            	}
            }
        }

Log in to reply
 

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