Let's Code_: 2022

Thursday, September 1, 2022

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:

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

Tuesday, July 19, 2022

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

Monday, July 18, 2022

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:

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

Saturday, May 7, 2022

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:

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

Tuesday, April 5, 2022

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:

// 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:

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

Let's Code_

Thursday, September 1, 2022

interviewBit Medium: Palindrome Partitioning II

Tuesday, July 19, 2022

Leetcode Medium: Container with most water

Monday, July 18, 2022

Leetcode Hard: Trapping Rain Water

Saturday, May 7, 2022

LeetCode Medium: Product of Array Except Self

Tuesday, April 5, 2022

Leetcode Medium: Set Matrix Zeroes

Leetcode Problem: Climbing Stairs

Featured Post

interviewBit Medium: Palindrome Partitioning II

Search This Blog