interviewBit Medium: Palindrome Partitioning II

Problem Name: Palindrome Partitioning II

Problem Description: https://www.interviewbit.com/problems/palindrome-partitioning-ii/

Problem Approach used: This problem can be solved with MCM approach. You can note this when you feel the urge to partition the input String into parts (which are palindromes themselves in this case). 

Time Complexity:  O(n^2) worst-case time complexity and O(n^2) auxiliary space for memoisation.

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 49 50 51 52 53 54 55 56

public class Solution { public int minCut(String A) { int memo[][] = new int[502][502]; for (int i=0; i<502; i++) { Arrays.fill (memo[i], -1); } // i=0, j=n-1 // to ensure 2 partitions return palinPartition(A, 0, A.length()-1, memo); } int palinPartition(String A, int i, int j, int [][] memo) { if (i >= j) { return 0; } if (isPalindrome(A, i, j)) { return 0; } if (memo[i][j] != -1) { return memo[i][j]; } int mn = Integer.MAX_VALUE; // k= i -> j-1 for (int k=i; k<j; k++) { int c1 = palinPartition(A, i, k, memo); int c2 = palinPartition(A, k+1, j, memo); int temp = c1+c2+1; mn = Math.min (mn, temp); } return memo[i][j] = mn; } boolean isPalindrome(String s, int i, int j) { if (i >= j) return true; while (i<j) { if (s.charAt(i) != s.charAt(j)) { return false; } else { i++; j--; } } return true; } }

Until Next time, Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

Leetcode Medium: Container with most water

Problem Name: Container with most water

Problem Description: https://leetcode.com/problems/container-with-most-water

Problem Approach used: This problem can be solved with multiple approaches. The naive solution calculates the water content in all possible containers, compares and returns the maximum water that can be contained. It is O(n^2) time solution with O(1) auxiliary space.

Other "smarter" solution takes O(n) time with O(1) space. It makes use of the 2-pointer technique. 

Time Complexity:  O(n) worst-case time complexity and O(1) auxiliary space complexity.

Solution 1:

class Solution { public int maxArea(int[] height) { int maxArea = Integer.MIN_VALUE; for (int i=0; i<height.length; i++) { for (int j=i+1; j<height.length; j++) { int lesserHeight = Math.min(height[i], height[j]); maxArea = Math.max (maxArea, lesserHeight*(j-i)); } } return maxArea; } }

Solution 2:

class Solution { public int maxArea(int[] height) { // 2 pointer technique int smallerIndex=0, greaterIndex=height.length-1; int maxAreaSoFar = 0; while (smallerIndex < greaterIndex) { if (height[smallerIndex] >= height[greaterIndex]) { maxAreaSoFar = Math.max(maxAreaSoFar, height[greaterIndex] * (greaterIndex - smallerIndex)); greaterIndex-- ; } else if (height[smallerIndex] < height[greaterIndex]) { maxAreaSoFar = Math.max(maxAreaSoFar, height[smallerIndex] * (greaterIndex - smallerIndex)); smallerIndex++; } else { ; } } return maxAreaSoFar; } }

Until Next time, Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

Leetcode Hard: Trapping Rain Water

 

Problem Name: Trapping Rain Water

Problem Description: https://leetcode.com/problems/trapping-rain-water/

Problem Approach used: Calculate the amount of water this index would store with the knowledge of highest left and highest right tower. Then subtract the hight of the current tower as that's just conctrete, water can't seep into.

Time Complexity:  O(n) worst-case time and 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

class Solution { public int trap(int[] height) { int n = height.length; int[] leftMax = new int[n]; int[] rightMax = new int[n]; int maxHt = 0; for (int i=0; i<n; i++) { maxHt = Math.max (maxHt, height[i]); leftMax[i] = maxHt; } maxHt = 0; for (int i=n-1; i>=0; i--) { maxHt = Math.max (maxHt, height[i]); rightMax[i] = maxHt; } int totalWater = 0; int water = 0; for (int i=0; i<n; i++) { water = Math.min(leftMax[i], rightMax[i]) - height[i]; totalWater += water; } return totalWater; } }

Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

LeetCode Medium: Product of Array Except Self

 Problem Name: Product of Array Except Self

Problem Description: https://leetcode.com/problems/product-of-array-except-self/

Problem Approach used: It's an easy problem to solve, just keep in mind your Indeterminate Numbers lesson of High School to solve it.

Time Complexity:  O(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

class Solution { public int[] productExceptSelf(int[] nums) { long prodArr = 1; long non0ProdArr = 1; int countZeroes = 0; for (int i=0; i<nums.length; i++) { if (nums[i] == 0) countZeroes++; if (nums[i] != 0) non0ProdArr *= nums[i]; prodArr *= nums[i]; } int[] answer = new int[nums.length]; if (countZeroes > 1) { Arrays.fill(answer, 0); return answer; } for (int i=0; i<nums.length; i++) { if (nums[i] == 0 && countZeroes == 1) { countZeroes--; answer[i] = (int)non0ProdArr; } else { answer[i] = (int)(prodArr / (long)nums[i]); } } return answer; } }

Until Next time, Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

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

 

LeetCode Medium: Generate Parentheses

Dear followers,

Tonight, I came across a nice problem for post-dinner exercise, about generating all possible valid parentheses sequences given the number of brackets to use in total.

PROBLEM LINK: https://leetcode.com/problems/generate-parentheses/

PROBLEM SOLVING APPROACH: Recursion (using Choice Diagram and Decision tree)

TIME-COMPLEXITY: O(2^n) in the worst case but the input n is given to be max 8, so very much doable :)

Here's a sample Java solution for your reference:

class Solution {
    public List<String> generateParenthesis(int n) {
        ArrayList<String> generatedParentheses = new ArrayList<>();
        genParenthesesRecur(n, n, "", generatedParentheses);
        return generatedParentheses;
    }
    
    private void genParenthesesRecur (int remOpenBrackets, int remClosingBrackets, String outputFromCaller, List<String> generatedParentheses) {
        // Base Cases
        if (remOpenBrackets < 0 || remClosingBrackets < 0)
            return;
        
        if (remClosingBrackets < remOpenBrackets) {
            return;
        }
        
        if (remOpenBrackets == 0 && remClosingBrackets == 0) {
           generatedParentheses.add(outputFromCaller);
        }
        
        // Recursive Case
        String opUsingAnOpeningBracket = outputFromCaller + "(";
        genParenthesesRecur(remOpenBrackets-1, remClosingBrackets, opUsingAnOpeningBracket, generatedParentheses);
        if (remClosingBrackets > remOpenBrackets) {
            String opUsingAClosingBracket = outputFromCaller + ")";
            genParenthesesRecur(remOpenBrackets, remClosingBrackets-1, opUsingAClosingBracket, generatedParentheses);
        }
    }
}

Thanks for Reading!

Happy Programming!!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder