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 Trick Problem: Longest Consecutive Sequence

Came across this problem on Leetcode, which requires one to focus on optimization.

PROBLEM LINK: https://leetcode.com/problems/longest-consecutive-sequence

TIME COMPLEXITY: O(n) at worst case where n is the number of elements in the input array (precisely the constant factor for n is 2)

APPROACH: The most naive approach to solve this problem would have been to sort the input array using comparison sort in O(n lg n) worst case time complexity and then in single pass find the length of the consecutive sequences in the same, resulting in overall worst case time complexity on O(n lg n).

But, if we notice carefully, we can make use of a trick to solve the problem in O(n) worst case time complexity. The trick makes a space trade off of O(n) and makes use of a HashSet to store the values to quickly check if any number exists in the input array. Then, it checks for all values in input, if it is the start of a consecutive sequence by checking presence of 1 lesser value than that on the number line, in the number Set. If any start-of-consecutive-range is found in the array elements, the length of the range is found by consecutively checking all the numbers in the increasing order on the number line consecutively.

In each such iteration of the numbers in input array, the length of the max-range is updated and the largest value is returned at the end of all iterations.

Here's a sample code for the same:

class Solution {
    
    public int longestConsecutive(int[] nums) {
        Set numberSet = new HashSet ();
        
        // Add numbers to Set while updating length of the longest consecutive elements sequence
        int maxLLCES = 0, currLLCES = 0;
        for (int i=0; i<nums.length; i++) {
            numberSet.add (nums[i]);
        }
        
        for (int i=0; i<nums.length; i++) {
            if (!numberSet.contains(nums[i]-1)) {
                // nums[i] is not a start of a consecutive sequence
                currLLCES = 1;
                int checkNum = nums[i]+1;
                while(numberSet.contains(checkNum)) {
                    currLLCES++;
                    checkNum++;
                }
                maxLLCES = Math.max(maxLLCES, currLLCES);
                // System.out.println("Updated maxLLCES:" + maxLLCES);
            }
        }
        return maxLLCES;
    }
}

Do share your thoughts and feel free to talk about the alternatives/optimisations you feel can be done in the comment section!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

 

LeetCode Medium: Course Schedule

 The next problem in the current coding spree was:

Problem Name: Course Schedule

Problem Description: https://leetcode.com/problems/course-schedule/

Problem Approach used: Detecting cycles on the directed graph pf dependencies using DFS to solve in O(V+E) where V is the number of courses in the input and E is the number of edges between them.

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

Java Solution:

//Cycle detection

// package com.projects.cv.course_schedule;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    // private static Logger logger = Logger.getLogger("MyLogger");
    int nodes;


    public boolean canFinish(int numCourses, int[][] prerequisites) {

        if (prerequisites == null)
            return false;
        int pL = prerequisites.length;
        nodes = numCourses;

        // Build directed graph
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i=0; i<pL; i++) {
            if (!g.containsKey(prerequisites[i][0]))
                g.put(prerequisites[i][0], new ArrayList<>());
            g.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }

        System.out.println(g);

        //Create visited to prevent re-visiting
        int visited[] = new int[numCourses];

        for (int i=0; i<numCourses; i++) {
            if (visited[i] == 0) {
                if (hasCycleDfs(g, visited, i, -1))
                    return false;
            }
        }

        return true;

    }

    private boolean hasCycleDfs( Map<Integer, List<Integer>> g, int[] visited, int n, int parent) {
        if (visited[n] == -1) {
            //current exploration path
            System.out.println("cycle found at u(" + parent + ")->v(" + n + ")");
            return true;
        }
        if (visited[n] == 1) {
            return false;
        }

        visited[n] = -1;

        if (g.get(n) == null) { // tackle bad callers
            visited[n] = 1;
            return false;
        }

        for (int neighBr : g.get(n)) {
            if (hasCycleDfs(g, visited, neighBr, n))
                return true;
        }

        visited[n] = 1;

        return false;
    }

    // public static void main(String[] args) {
    //     Solution s = new Solution();
    //     int[][] deps = {{1, 0}};
    //     s.canFinish(2, deps);
    // }

}

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

 

GeeksforGeeks Medium: Find the Number of Islands

Yesterday I solved a few hands-on coding problems using Java programming language.

I came across this easy problem(called Medium there) over GfG, to turn on the inertia:

Problem: Find the Number of Islands

Problem Description: https://practice.geeksforgeeks.org/problems/find-the-number-of-islands 

Problem Approach: DFS

Time Complexity: O(V) where v = number of cells in the input grid

One Java Solution:

// { Driver Code Starts
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            String[] s = br.readLine().trim().split(" ");
            int n = Integer.parseInt(s[0]);
            int m = Integer.parseInt(s[1]);
            char[][] grid = new char[n][m];
            for(int i = 0; i < n; i++){
                String[] S = br.readLine().trim().split(" ");
                for(int j = 0; j < m; j++){
                    grid[i][j] = S[j].charAt(0);
                }
            }
            Solution obj = new Solution();
            int ans = obj.numIslands(grid);
            System.out.println(ans);
        }
    }
}// } Driver Code Ends



class Solution
{
    int r, c;
    byte[] xOffset = {1, 1, 1, 0, -1, -1, -1, 0};
    byte[] yOffset = {1, 0, -1, -1, -1, 0, 1, 1};
    
    //Function to find the number of islands.
    public int numIslands(char[][] grid)
    {
        // Code here
        r = grid.length;
        c = grid[0].length;
        
        boolean[][] visited = new boolean[r][c];
        int cnt = 0;
        for (int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if (grid[i][j]=='1' && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
    
    private void dfs (char[][] grid, boolean[][] visited, int x, int y) {
        //input validation
        if (!valid (grid, x, y) || visited[x][y]==true) {
            return;
        }
        
        visited[x][y] = true;
        
        for (int i=0; i<8; i++) {
            int newX = x + xOffset[i];
            int newY = y + yOffset[i];
            
            if(valid(grid, newX, newY) && !visited[newX][newY]) {
                dfs(grid, visited, newX, newY);
            }
        }
    }
    
    boolean valid (char[][]grid, int x, int y) {
        if (x<0 || x>=r || y<0 || y>=c || grid[x][y] == '0'){
            return false;
        }
        return true;
    }
}

Do share your thoughts and feel free to talk about the alternatives/optimisations you feel can be done in the comment section!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

 https://www.facebook.com/theAlgorithmicCoder

 

 

HackerRank: Reverse a doubly linked list

Problem Description: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem

Runtime complexity of my below code: O(n) where n is the size of the linked list.

Solution approach: Recursive

My Java 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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135

import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { static class DoublyLinkedListNode { public int data; public DoublyLinkedListNode next; public DoublyLinkedListNode prev; public DoublyLinkedListNode(int nodeData) { this.data = nodeData; this.next = null; this.prev = null; } } static class DoublyLinkedList { public DoublyLinkedListNode head; public DoublyLinkedListNode tail; public DoublyLinkedList() { this.head = null; this.tail = null; } public void insertNode(int nodeData) { DoublyLinkedListNode node = new DoublyLinkedListNode(nodeData); if (this.head == null) { this.head = node; } else { this.tail.next = node; node.prev = this.tail; } this.tail = node; } } public static void printDoublyLinkedList(DoublyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException { while (node != null) { bufferedWriter.write(String.valueOf(node.data)); node = node.next; if (node != null) { bufferedWriter.write(sep); } } } // Complete the reverse function below. /* * For your reference: * * DoublyLinkedListNode { * int data; * DoublyLinkedListNode next; * DoublyLinkedListNode prev; * } * */ static DoublyLinkedListNode reverse(DoublyLinkedListNode head) { return reverseRecur(head, head.next); } private static DoublyLinkedListNode reverseRecur(DoublyLinkedListNode current, DoublyLinkedListNode nextNode) { // 2, 3 3, 4 4, \0 if (current == null) return current; if (nextNode == null && current.prev == null) { return current; } //Node nextNode = current.next; 2 DoublyLinkedListNode prevNode = current.prev; // \0 1 2 3 if (nextNode == null) { current.prev = null; return current; // 4 } //Assume reversed till current. DoublyLinkedListNode nextToNext = nextNode.next; // 4 \0 // 1 <-> 2 <-> 3 <-> 4 -> 4<->3<->2<->1 nextNode.next = current; //4 <-> 3 <-> 2 <-> 1 -> \0 current.prev = nextNode; current.next = prevNode; return reverseRecur(nextNode, nextToNext); // 3, 4 4, \0 } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int t = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int tItr = 0; tItr < t; tItr++) { DoublyLinkedList llist = new DoublyLinkedList(); int llistCount = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < llistCount; i++) { int llistItem = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); llist.insertNode(llistItem); } DoublyLinkedListNode llist1 = reverse(llist.head); printDoublyLinkedList(llist1, " ", bufferedWriter); bufferedWriter.newLine(); } bufferedWriter.close(); scanner.close(); } }

Do share your thoughts below!

Until next time, Happy Coding!

Become a Patron!

LeetCode Medium: Open the Lock

 Another BFS solvable problem of LeetCode!

Problem Description: https://leetcode.com/problems/open-the-lock/

Problem Approach: BFS

Time Complexity: O(1) as the custom size of state-nodes in this problem is a constant.

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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

//public class OpenTheLock { //} import java.util.*; class State { String code; int dist; State(String code, int dist) { this.code = code; this.dist = dist; } } class Solution { public int openLock(String[] deadends, String target) { Set<String> visited = new HashSet<>(); Set<String> deadendsSet = new HashSet<>(); for (String d : deadends) { deadendsSet.add(d); } if ("0000".equals(target)) return 0; if (deadendsSet.contains("0000")) return -1; Queue<State> q = new LinkedList<>(); q.add(new State("0000", 0)); visited.add("0000"); while (!q.isEmpty()) { State out = q.remove(); List<String> neighbours = getNeighbours(out.code); for (String n : neighbours) { if (!visited.contains(n) && !deadendsSet.contains(n)) { if (n.equals(target)) return out.dist+1; State neighState = new State(n, out.dist+1); visited.add(n); q.add(neighState); } } } return -1; } private List<String> getNeighbours(String baseState) { List<String> res = new ArrayList<>(); char[] codeChar = baseState.toCharArray(); for (int i=0; i<codeChar.length; i++) { String neighState = new String(); String c = ((codeChar[i]-'0')+1)%10 + ""; for (int idx=0; idx<codeChar.length; idx++) if (idx == i) neighState+=c; else neighState+=codeChar[idx]; res.add(neighState); neighState = new String(); c = ((codeChar[i]-'0')+10-1)%10 + ""; for (int idx=0; idx<codeChar.length; idx++) if (idx == i) neighState+=c; else neighState+=codeChar[idx]; res.add(neighState); } return res; } }

Have fun, until next time!

Become a Patron!