Sunday, August 29, 2021

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

 




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

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

 

 



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

Restarting Shorter and More Intense Problem-Solving Sprints

Hello Fellas,


After a long break, I have re-started #Problem #Solving #Tutorials using DS/Algorithms over (this) Let's Code Blog, but this time, it's gonna be consisting more intense but shorter #Coding #Sprints over weekends and somewhat lesser live-videos!! :D

Join me and get the weekend puzzle-solver activated in you!


✌️
#LetsCode
at No comments:
Labels:

Sunday, February 14, 2021

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!


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

Saturday, January 23, 2021

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!

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

LeetCode Medium: Snakes and Ladders

Here's a problem based on the classical snakes and ladders children's game


Problem Description: https://leetcode.com/problems/snakes-and-ladders

Solution Approach: BFS

Time Complexity: O(V) where V is the number of cells in the board-game and E = 6V.


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
class Solution {
    public int snakesAndLadders(int[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        int maxSq = rows*cols;
        
        boolean visited[] = new boolean[maxSq];
        int[] pred = new int[maxSq+1]; // Allows to print the path as well. Alternatively, a dist[] incrementing at each time can be used too.
        Queue<Integer> squaresQ = new LinkedList<>();
        squaresQ.add(1);
        visited[1] = true;
        pred[1] = 0;
        
        outer:
        while(!squaresQ.isEmpty()) {
            int sqOut = squaresQ.remove();
            
            for (int i=1; i<=6; i++) {
                int neighbourSq = sqOut + i;
                if (neighbourSq > maxSq)
                    break;
                
                int effRow = getEffRow(neighbourSq, rows, cols);
                int effCol = getEffCol(neighbourSq, rows, cols);
                if (board[effRow][effCol] != -1) {
                    neighbourSq = board[effRow][effCol];
                    effRow = getEffRow(neighbourSq, rows, cols);
                    effCol = getEffCol(neighbourSq, rows, cols);
                }
                if (neighbourSq == maxSq) {
                    pred[neighbourSq] = sqOut;
                    break outer;
                }
                
                if (!visited[neighbourSq]) {
                    visited[neighbourSq] = true;
                    pred[neighbourSq] = sqOut; // Alternatively, can do: dist[neighbourSq] = dist[sqOut]++;
                    squaresQ.add(neighbourSq);
                }
                
            }
        }
        
        int cnt = 0;
        int predSq = maxSq;
        if (pred[predSq] == 0)
            return -1;
        while(predSq != 1) {
            cnt++;
            predSq = pred[predSq];
        }
        
        return cnt;
    }
    
    private int getEffRow(int sq, int rows, int cols) {
       return (rows - 1 - (sq-1)/cols);
    }
    
    private int getEffCol(int sq, int rows, int cols) {
        int effCol = (sq -1) % cols; // 0 based
        
        if (((sq - 1)/cols + 1) % 2 == 0) // even row from bottom:1 based
            effCol = cols - 1 - effCol;
        
        return effCol;
    }
}


Until next time,

Happy Coding!

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

Monday, January 18, 2021

LeetCode Medium: Pancake Sorting

Problem of the day: Pancake Sorting

Problem description: https://leetcode.com/problems/pancake-sorting/

Solution Approach:

At every iteration for n-1 iterations move the max element in unsorted prefix array to the end of it by following the following steps:

  1. Find max element index in unsorted prefix part.
  2. flip array at that index.
  3. flip array at index marking the end of unsorted array.
  4. reduce the pointer marking end of unsorted array by 1 thereby decreasing the unsorted part of the array.

Solution:


  
  class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        if (arr.length<=1) {
            return new ArrayList<>();
        }
        
        List<Integer> maxIndicesSelectedForFlip;
        
        int endOfUnsortedArray = arr.length-1;
        for (int idx=1; idx <= endOfUnsortedArray; idx++) {
            //find maxElement, maxElementIndex
            int maxElement = Integer.MIN_VALUE, maxElementIndex = -1;
            for (int i=0; i < endOfUnsortedArray; i++) {
                if (arr[i]>maxElement) {
                    maxElement = arr[i];
                    maxElementIndex = i;
                }
            }

            //Flip 0->maxElementIndex
            flip(arr, maxElementIndex);
            maxIndicesSelectedForFlip.add(maxElementIndex+1);

            //Flip 0->endOfUnsortedArray
            flip(arr, endOfUnsortedArray);
            maxIndicesSelectedForFlip.add(endOfUnsortedArray+1);
        }
        
        return maxIndicesSelectedForFlip;
        
    }
    
    private void flip(int[] arr, int maxIndex) {
        for (int i=0; i<=maxIndex/2; i++) {
            int tmp = arr[i];
            arr[i] = arr[maxIndex-i];
            arr[maxIndex-i] = tmp;
        }
    }
    
}

Time Complexity: O(n^2)

Space Complexity: In-place sorting: O(1) 


Happy Coding! ;)

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