Leetcode Medium: Set Matrix Zeroes

 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 :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

 

Leetcode Problem: Climbing Stairs

 Problem of Today: Climbing Stairs

Problem description: https://leetcode.com/problems/climbing-stairs/

Solution Approach: Memoization

Solution: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { private int memo[]; // Bottom-up public int climbStairs(int n) { memo = new int[n+1]; for (int i=0; i<=n; i++) { memo[n] = -1; } memo[0] = 1; memo[1] = 1; for (int i=2; i<=n; i++) { memo[i] = memo[i-1] + memo[i-2]; } return memo[n]; } }

Happy Coding!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder