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

 

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!

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!

Become a Patron!