Showing posts with label Arrays. Show all posts
Showing posts with label Arrays. Show all posts

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:

 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





at No comments:
Labels: , , , , , , , , , , , , , , , , , , ,

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












at





No comments:
  























Labels:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,

















          

        

          

        

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














at





No comments:
  























Labels:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,






















          

        

          

        

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













at





No comments:
  























Labels:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,

















        

      









Subscribe to:
Posts (Atom)







Featured Post




interviewBit Medium: Palindrome Partitioning II



Problem Name:  Palindrome Partitioning II Problem Description : https://www.interviewbit.com/problems/palindrome-partitioning-ii/ Problem Ap...