Problem Name: Set Matrix Zeroes
Problem Description: https://leetcode.com/problems/set-matrix-zeroes/
Problem Approach used: Its a trick problem to solve it in constant space. We've used the same, using HashSets in the below solution.
Time Complexity: O(m*n) worst-case time complexity and O(1) auxiliary space complexity.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | // In 1 line of thought, constant space solution is ideally not possible as all possible int values can be part of the matrix, but if we can assume some sentinel value out of these (like Integer.MIN_VALUE in our case) for marking original zeroes, a solution follows. // * Also we can use a trick to solve ths problem: marking 1st(top and left) elements of the row and column respetively, to 0. class Solution { Set<Integer> toZeroRows = new HashSet<>(), toZeroColumns = new HashSet<>(); public void setZeroes(int[][] matrix) { for (int row=0; row<matrix.length; row++) { for (int column=0; column<matrix[0].length; column++) { if (matrix[row][column] == 0) { toZeroRows.add(row); toZeroColumns.add(column); } } } // Print initial matrix printMatrix(matrix); for (int row=0; row<matrix.length; row++) { if (toZeroRows.contains(row)) { for(int columnIndex=0; columnIndex<matrix[0].length; columnIndex++) { matrix[row][columnIndex] = 0; } } } printMatrix(matrix); for (int column=0; column<matrix[0].length; column++) { if (toZeroColumns.contains(column)) for(int rowIndex=0; rowIndex<matrix.length; rowIndex++) { matrix[rowIndex][column] = 0; } } printMatrix(matrix); } public void printMatrix(int [][] matrix) { for (int row = 0; row<matrix.length; row++) { for (int column = 0; column<matrix[0].length; column++) { System.out.print(" " + matrix[row][column]); } System.out.println(); } } } |
Happy Coding!
Love! ❤️
#Lets #Code
Follow us on :
