207. Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

Solution:

This is a topological order question.

It asks whether the courses can be formed a topological order.

Therefore we use a count variable to store the number of courses that can form such order.

If it equals to the total number of courses, we return true.



Code:

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        int[] degree = new int[numCourses];
        for (int[] pair : prerequisites) {
            int courseFrom = pair[1];
            int courseTo = pair[0];
            adj[courseFrom].add(courseTo);
            degree[courseTo]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.offer(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int nei : adj[course]) {
                degree[nei]--;
                if (degree[nei] == 0) {
                    queue.offer(nei);
                }
            }
        }
        return count == numCourses;
    }
}

269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

Solution:

The idea is to use topological sort to get the order of characters.

To build the graph, we compare every two adjacent words.

If we found the character in the same index different, we know the order of these two characters, and thus add an edge and update the indegree.

After building the graph, we simply apply topological sort.



Code:

public class Solution {
    public String alienOrder(String[] words) {
        ArrayList<Character>[] adj = new ArrayList[26];
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<Character>();
        }
        
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (indegree[c - 'a'] < 0) {
                    indegree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 == c2) {
                    if (j == w2.length() - 1 && w1.length() > w2.length()) {
                        return "";
                    }
                    continue;
                }
                if (!adj[c1 - 'a'].contains(c2)) {
                    adj[c1 - 'a'].add(c2);
                    indegree[c2 - 'a']++;
                }
                break;
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (indegree[i] == 0) {
                queue.offer((char)('a' + i));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            for (char nei : adj[c - 'a']) {
                indegree[nei - 'a']--;
                if (indegree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int d : indegree) {
            if (d > 0) {
                return "";
            }
        }
        return sb.toString();
    }
}

Use HashMap

public class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        StringBuilder order = new StringBuilder();
        HashMap<Character, HashSet<Character>> adj = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            adj.put(c, new HashSet<Character>());
        }
        int[] degree = new int[26];
        Arrays.fill(degree, -1);
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (degree[c - 'a'] == -1) {
                    degree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (!adj.get(c1).contains(c2)) {
                        adj.get(c1).add(c2);
                        degree[c2 - 'a']++;  
                    }
                    break;
                }
                if (j == w2.length() - 1 && w1.length() > w2.length()) {
                    return "";
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (degree[i] == 0) {
                queue.offer((char)(i + 'a'));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char nei : adj.get(c)) {
                if (--degree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (degree[i] > 0) {
                return "";
            }
        }
        return order.toString();
    }
}

261. Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution:

Method 1: BFS

If a graph is a valid tree, it satisfies:

1. If and only if the number of edges equals n - 1.

2. All n vertices are connected.

We use BFS to traverse the graph and store all reached vertices to a HashSet.

After traversing, we check if the size of HashSet is n.



Code:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return false;
        }
        if (edges.length != n - 1) {
            return false;
        }
        
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        
        HashSet<Integer> set = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        set.add(0);
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int neighbor : adj[v]) {
                if (!set.contains(neighbor)) {
                    set.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return set.size() == n;
    }
}

Method 2: Union Find


Code:

210. Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

Hints:

1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

Solution:

Kahn's algorithm

One of these algorithms, first described by Kahn (1962), works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

If the graph is a DAG, a solution will be contained in the list L (the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sorting is impossible.

Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties lexicographically forms a key component of the Coffman–Graham algorithm for parallel scheduling and layered graph drawing.

Code:

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] adj = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        int[] order = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        
        for (int[] pre : prerequisites) {
            adj[pre[1]].add(pre[0]);
            indegree[pre[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[count++] = course;
            for (int neighbor : adj[course]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        if (count == numCourses) {
            return order;
        }
        
        return new int[0];
    }
}

133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution:

Method 1: BFS

We use BFS to traverse the graph.

When we meet a node, we make a copy of it and store it into the HashMap.

We also check all its neighbors.

If any of its neighbor is not in the HashMap, we make a copy of it and store in the HashMap.

One more step: add this neighbor to the neighbor list of the current node we check.

The time complexity is O(n) and space complexity is also O(n).



Code:

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode nei : curr.neighbors) {
                if (!map.containsKey(nei)) {
                    map.put(nei, new UndirectedGraphNode(nei.label));
                    queue.add(nei);
                }
                map.get(curr).neighbors.add(map.get(nei));
            }
        }
        return map.get(node);
    }
}