## Monday, April 25, 2016

### LeetCode 207 - Course Schedule I

https://leetcode.com/problems/course-schedule/
Related: LeetCode 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, 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:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

• Topological sorting
• Like all graph search algorithm: O(E+V)
• 题目等价为：检测图中是否有环
X. Topological Sort
https://leetcode.com/discuss/34699/my-java-bfs-solution
Use Map<Integer, ArrayList<Integer>>
public boolean canFinish(int numCourses, int[][] prerequisites) { Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); int[] indegree = new int[numCourses]; Queue<Integer> queue = new LinkedList<Integer>(); int count = numCourses; for (int i = 0; i < numCourses; i++) { map.put(i, new ArrayList<Integer>()); } for (int i = 0; i < prerequisites.length; i++) { map.get(prerequisites[i][0]).add(prerequisites[i][1]); indegree[prerequisites[i][1]]++; } for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) { queue.offer(i); } } while (!queue.isEmpty()) { int current = queue.poll(); for (int i : map.get(current)) { if (--indegree[i] == 0) { queue.offer(i); } } count--; } return count == 0; }
`https://leetcode.com/discuss/37134/java-ac-solution-with-top-sort`
`Use hashset - not really better`
```    public boolean canFinish(int numCourses, int[][] prerequisites) {
Set<Integer> zeroDegree = new HashSet<>();
int[] degree = new int[numCourses];
for (int row = 0; row < prerequisites.length; row++)
degree[prerequisites[row][0]]++;
for (int i = 0; i < degree.length; i++)
if (degree[i] == 0) zeroDegree.add(i);
if (zeroDegree.isEmpty()) return false;
while (!zeroDegree.isEmpty()) {
Iterator<Integer> it = zeroDegree.iterator();
int course = it.next();
zeroDegree.remove(course);
for (int row = 0; row < prerequisites.length; row++) {
int[] edge = prerequisites[row];
if (edge[1] == course) {
degree[edge[0]]--;
if (degree[edge[0]] == 0) zeroDegree.add(edge[0]);
}
}
}
for (int i = 0; i < degree.length; i++)
if (degree[i] != 0) return false;
return true;
}```
```not efficient
https://leetcode.com/discuss/35578/easy-bfs-topological-sort-java```
http://www.programcreek.com/2014/05/leetcode-course-schedule-java/
https://leetcode.com/discuss/82347/java-easy-version-to-understand
 ```public boolean canFinish(int numCourses, int[][] prerequisites) { if(prerequisites == null){ throw new IllegalArgumentException("illegal prerequisites array"); }   int len = prerequisites.length;   if(numCourses == 0 || len == 0){ return true; }   // counter for number of prerequisites int[] pCounter = new int[numCourses]; for(int i=0; i queue = new LinkedList(); for(int i=0; i

https://leetcode.com/discuss/39456/java-dfs-and-bfs-solution
public boolean canFinish(int numCourses, int[][] prerequisites) { ArrayList[] graph = new ArrayList[numCourses]; int[] degree = new int[numCourses]; Queue queue = new LinkedList(); int count=0; for(int i=0;i<numCourses;i++) graph[i] = new ArrayList(); for(int i=0; i<prerequisites.length;i++){ degree[prerequisites[i][1]]++; graph[prerequisites[i][0]].add(prerequisites[i][1]); } for(int i=0; i<degree.length;i++){ if(degree[i] == 0){ queue.add(i); count++; } } while(queue.size() != 0){ int course = (int)queue.poll(); for(int i=0; i<graph[course].size();i++){ int pointer = (int)graph[course].get(i); degree[pointer]--; if(degree[pointer] == 0){ queue.add(pointer); count++; } } } if(count == numCourses) return true; else return false; }

X. Using
https://discuss.leetcode.com/topic/13854/easy-bfs-topological-sort-java

Could you provide the Time complexity for your solution using adjacent matrix?`
``````while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int i=0; i<numCourses; i++) {
if (matrix[course][i] != 0) {
if (--indegree[i] == 0)
queue.offer(i);
}
}
}
``````
For this part, I kind of guess it is not O(V^2) instead of O(V+E) because you always scan from i=0 to numCourses to check whether the matrix[course][i] is 0 or not.
Is this solution memory-efficient? The matrix seems to be a big overhead.

``````public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] matrix = new int[numCourses][numCourses]; // i -> j
int[] indegree = new int[numCourses];

for (int i=0; i<prerequisites.length; i++) {
int ready = prerequisites[i][0];
int pre = prerequisites[i][1];
if (matrix[pre][ready] == 0)
}

int count = 0;
Queue<Integer> queue = new LinkedList();
for (int i=0; i<indegree.length; i++) {
if (indegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int i=0; i<numCourses; i++) {
if (matrix[course][i] != 0) {
if (--indegree[i] == 0)
queue.offer(i);
}
}
}
return count == numCourses;
}``````
I rewrote the code, I think that would be O(V + E)
``````    // O(V + E)
List<Integer>[] matrix = new List[numCourses];
int[] indegree = new int[numCourses];

// E part
for (int[] pre : prerequisites) {
int preCourse = pre[1];
int readyCourse = pre[0];
List<Integer> list = matrix[preCourse];
if (list == null) {
list = new LinkedList<>();
matrix[preCourse] = list;
}
}

Queue<Integer> queue = new LinkedList<>();
for (int i=0; i<numCourses; i++) {
if (indegree[i] == 0) queue.offer(i);
}
int count = 0;
// V part
while (!queue.isEmpty()) {
int vertex = queue.poll();
count++;
List<Integer> adjacent = matrix[vertex];
if (adjacent == null) continue;
for (int neighbor : adjacent) {
indegree[neighbor]--;
if (indegree[neighbor] == 0)
queue.offer(neighbor);
}
}
return count == numCourses;``````
https://leetcode.com/discuss/71444/explained-java-12ms-iterative-solution-based-algorithm-clrs
Not efficient to use ArrayList as a queue.
X. DFS
https://leetcode.com/discuss/65901/concise-java-solutions-based-on-bfs-and-dfs-with-explanation
To do memorization and pruning, a HashMap is used to save the previous results for the specific node.
``````HashMap<Integer, Boolean>memo = new HashMap<Integer, Boolean>();//Memorization HashMap for DFS pruning
public boolean canFinish(int n, int[][] edges) {
if (edges.length != 0) {
HashMap<Integer, HashSet<Integer>> neighbors = new HashMap<Integer, HashSet<Integer>>(); // Neighbors of each node
HashSet<Integer>curPath = new HashSet<Integer>(); // Nodes on the current path
for (int i = 0; i < edges.length; i++) {// Convert graph presentation from edge list to adjacency list
if (!neighbors.containsKey(edges[i][1]))
neighbors.put(edges[i][1], new HashSet<Integer>());
}

for (int a[] : edges) // The graph is possibly not connected, so need to check every node.
if (hasCycle(neighbors, a[0], -1, curPath))// Use DFS method to check if there's cycle in any curPath
return false;
}
return true;
}

boolean hasCycle(HashMap<Integer, HashSet<Integer>> neighbors, int kid, int parent, HashSet<Integer>curPath) {
if (memo.containsKey(kid)) return memo.get(kid);
if (curPath.contains(kid)) return true;// The current node is already in the set of the current path
if (!neighbors.containsKey(kid)) return false;

for (Integer neighbor : neighbors.get(kid)) {
boolean hasCycle = hasCycle(neighbors, neighbor, kid, curPath);// DFS
memo.put(kid, hasCycle);
if (hasCycle) return true;
}
curPath.remove(kid);
return false;
}
```

```
http://buttercola.blogspot.com/2015/08/leetcode-course-schedule.html
Use an array to mark if the node has been visited before. Here is a small trick to save some time. Instead of using a boolean array, we use an integer array int[] visited.
visited = -1, means this node has been visited.
visited = 1, means this node has been validated which does not include a circle. Thus if we saw that a node has been validated, we don't need to calculate again to find out the circle starting from this node. e.g. [0, 1] [1, 2] [2, 3] [3, 4]. For the node 0, we have already validated 2 3 and 4 do not have a circle. Thus we don't need to calculate for the node 2 3 4 again.
`    ``public` `boolean` `canFinish(``int` `numCourses, ``int``[][] prerequisites) {`
`        ``if` `(numCourses <= ``0``) {`
`            ``return` `true``;`
`        ``}`
`        `
`        ``if` `(prerequisites == ``null` `|| prerequisites.length == ``0``) {`
`            ``return` `true``;`
`        ``}`
`        `
`        ``// First transform the edge list to adj. list`
`        ``Map<Integer, List<Integer>> adjList = ``new` `HashMap<>();`
`        ``for` `(``int``[] edge : prerequisites) {`
`            ``if` `(adjList.containsKey(edge[``0``])) {`
`                ``List<Integer> neighbors = adjList.get(edge[``0``]);`
`                ``neighbors.add(edge[``1``]);`
`                ``adjList.put(edge[``0``], neighbors);`
`            ``} ``else` `{`
`                ``List<Integer> neighbors = ``new` `ArrayList<Integer>();`
`                ``neighbors.add(edge[``1``]);`
`                ``adjList.put(edge[``0``], neighbors);`
`            ``}`
`        ``}`
`        `
`        ``int``[] visited = ``new` `int``[numCourses];`
`        ``// Check if the graph contains a circle, if yes, return false.`
`        ``for` `(``int` `i = ``0``; i < numCourses; i++) {`
`            ``if` `(hasCircles(i, visited, adjList)) {`
`                ``return` `false``;`
`            ``}`
`        ``}`
`        `
`        ``return` `true``;`
`    ``}`
`    `
`    ``private` `boolean` `hasCircles(``int` `vertexId, ``int``[] visited, Map<Integer, List<Integer>> adjList) {`
`        ``if` `(visited[vertexId] == -``1``) {`
`            ``return` `true``;`
`        ``}`
`        `
`        ``if` `(visited[vertexId] == ``1``) {`
`            ``return` `false``;`
`        ``}`
`        `
`        ``visited[vertexId] = -``1``;// wrong`
`        `
`        ``List<Integer> neighbors = adjList.get(vertexId);`
`        ``if` `(neighbors != ``null``) {`
`            ``for` `(``int` `neighbor : neighbors) {`
`                ``if` `(hasCircles(neighbor, visited, adjList)) {`
`                    ``return` `true``;`
`                ``}`
`            ``}`
`        ``}`
`        `
`        ``visited[vertexId] = ``1``;`
`        `
`        ``return` `false``;`
`    ``}`

 ```public boolean canFinish(int numCourses, int[][] prerequisites) { if(prerequisites == null){ throw new IllegalArgumentException("illegal prerequisites array"); }   int len = prerequisites.length;   if(numCourses == 0 || len == 0){ return true; }   //track visited courses int[] visit = new int[numCourses];   // use the map to store what courses depend on a course HashMap> map = new HashMap>(); for(int[] a: prerequisites){ if(map.containsKey(a[1])){ map.get(a[1]).add(a[0]); }else{ ArrayList l = new ArrayList(); l.add(a[0]); map.put(a[1], l); } }   for(int i=0; i> map, int[] visit, int i){ if(visit[i]==-1) return false; if(visit[i]==1) return true;   visit[i]=-1; if(map.containsKey(i)){ for(int j: map.get(i)){ if(!canFinishDFS(map, visit, j)) return false; } }   visit[i]=1;   return true; }```

http://happycoding2010.blogspot.com/2015/10/leetcode-207-course-schedule.html
`````` public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int V=numCourses;
for (int v=0; v<V; v++) adj[v]=new LinkedList<>();
boolean[] marked=new boolean[V];
boolean[] onStack=new boolean[V];
boolean[] hasCycle=new boolean[1];
for (int v=0; v<V; v++)
return !hasCycle[0];
}
private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle) {
marked[v]=true;
onStack[v]=true;
for (int w: adj[v]) {
if (hasCycle[0]) return;
else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle);
else if (onStack[w]) hasCycle[0]=true;
}
onStack[v]=false;
}
} ``````

http://sgq626.blogspot.com/2015/07/leetcode-207leetcode-210-course.html

这个题目里面没有 sanity check ！！！ 面试的时候要跟面试官商量sanity check的问题。
bool dfs(map<int, vector<int>> &nmap, int start, vector<int> &M) {
//base case
if (M[start] == 1) return true;//has visited
if (M[start] == -1) {
return false;
}
M[start] = -1; //visiting node
//expand
for (int i = 0; i < nmap[start].size();i++) {
if(dfs(nmap, nmap[start][i], M) == false) return false;
}
M[start] = 1; //mark visit
return true;
}
//to check if a directed graph has a cycle or not
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
//map
map<int, vector<int>> nmap;
for (int i = 0; i < prerequisites.size(); i++) {
nmap[prerequisites[i].second].push_back(prerequisites[i].first);//prere->course
}
//use map to do dfs + visit
vector<int> M(numCourses, 0); //unvisited
for (int i = 0; i < numCourses;i++) {
if (dfs(nmap, i, M) == false) return false;
}

return true;
}

http://felixzhang00.github.io/2015/05/07/2015-05-07-LeetCode%E7%AC%AC207%E9%A2%98--Course%20Schedule/
public boolean canFinish(int numCourses, int[][] prerequisites) {
Digraph G = new Digraph(numCourses);
for (int i = 0; i < prerequisites.length; i++) {
for (int j = 0; j < prerequisites[i].length; j++) {
}
}
DirectedCycle dag = new DirectedCycle(G);
return !dag.hasCycle();
}

onStack[v]=true,记录顶点v出现在这次dfs中，在这次dfs结束后，是onStack[v]=false

private class DirectedCycle {
private boolean[] marked;        // marked[v] 顶点v是否被访问过
private boolean[] onStack;       //保存递归调用期间栈上的所有顶点。 onStack[v] = ？顶点v是否在栈中
private boolean hasCycle;       // 有向图中是否环
public DirectedCycle(Digraph G) {
marked = new boolean[G.V()];
onStack = new boolean[G.V()];
hasCycle = false;
for (int v = 0; v < G.V(); v++)   //对图中每一个没有被访问过的点做深度优先遍历
if (!marked[v]) dfs(G, v);
}
/**
* 从v顶点开始做深度优先遍历
*/
private void dfs(Digraph G, int v) {
onStack[v] = true;
marked[v] = true;
for (int w : G.adj(v)) {        //遍历所有顶点v的相连点
if (hasCycle) return;       //如果已经找到一个环就不再dfs
else if (!marked[w]) {      //对每一个未访问过的点继续dfs
dfs(G, w);
} else if (onStack[w]) {    //顶点w在之前的递归调用栈中，并且已经被访问过，构成环
hasCycle = true;
}
}
onStack[v] = false;             //顶点v所有的相连点遍历结束,顶点v退出当前调用栈
}
public boolean hasCycle() {
return hasCycle;
}
}
private class Digraph {
private final int V;
public Digraph(int V) {
this.V = V;
adj = (ArrayList<Integer>[]) new ArrayList[V];
for (int v = 0; v < V; v++) {
adj[v] = new ArrayList<Integer>();
}
}
public void addEdge(int v, int w) {
}
public int V() {
return V;
}
public Iterable<Integer> adj(int v) {
}
}
X. Not efficient
https://leetcode.com/discuss/39456/java-dfs-and-bfs-solution
i second this. I may be wrong, but the worst case runtime could be n^2 since you are not checking if any nodes are visited in the main for loop (the one in the canFinish function). This means you may be doing repeated searches. Imagine 1->2->3->4->5, when checking node (1) in the main loop, you'll be go through 2 - 5, but when you r checking node(2) in the main loop, you'll go through 3 - 5 again.
The run time for this DFS solution is `O(V + E^2)`. In the worst case described above by OBOBOB90 the algorithm needs to iterate over each course (which is `O(V)`), plus V^2 time to iterate over the course dependencies (`O(E^2)`).
It is possible though to implement DFS algorithm with `O(E)` runtime
public boolean canFinish(int numCourses, int[][] prerequisites) { ArrayList[] graph = new ArrayList[numCourses]; for(int i=0;i<numCourses;i++) graph[i] = new ArrayList(); boolean[] visited = new boolean[numCourses]; for(int i=0; i<prerequisites.length;i++){ graph[prerequisites[i][1]].add(prerequisites[i][0]); } for(int i=0; i<numCourses; i++){ if(!dfs(graph,visited,i)) return false; } return true; } private boolean dfs(ArrayList[] graph, boolean[] visited, int course){ if(visited[course]) return false; else visited[course] = true;; for(int i=0; i<graph[course].size();i++){ if(!dfs(graph,visited,(int)graph[course].get(i))) return false; } visited[course] = false; return true; }

OO:

Build Order:
You are given a list of projects and a list of dependencies (which is a list of pairs of
projects, where the second project is dependent on the first project). All of a project's dependencies
must be built before the project is. Find a build order that will allow the projects to be built. If there
is no valid build order, return an error.
Project[] findBuildOrder(String[] projects, String[][] dependencies) {
Graph graph= buildGraph(projects, dependencies);
return orderProjects(graph.getNodes());
}

/* Build the graph, adding the edge (a, b) if b is dependent on a. Assumes a pair
* is listed in "build order". The pair (a, b) in dependencies indicates that b
* depends on a and a must be built before b. */
Graph buildGraph(String[] projects, String[][] dependencies) {
Graph graph= new Graph();
for (String project : projects) {
graph.createNode(project);
}

for (String[] dependency : dependencies) {
String first= dependency[0];
String second= dependency[l];
}

return graph;
}

/* Return a list of the projects a correct build order.*/
Project[] orderProjects(Arraylist<Project> projects) {
Project[] order = new Project[projects.size()];// if there are a lot of projects: use queue to remove already processed nodes

/* Add "roots" to the build order first.*/
int endOfList = addNonDependent(order, projects, 0);

int toBeProcessed = 0;
while (toBeProcessed < order.length) {
Project current= order[toBeProcessed];

/* We have a circular dependency since there are no remaining projects with
* zero dependencies. */
if (current== null) {
return null;
}

/* Remove myself as a dependency. */
Arraylist<Project> children = current.getChildren();
for (Project child : children) {
child.decrementDependencies();
}

/* Add children that have no one depending on them. */
endOfList = addNonDependent(order, children, endOfList);
toBeProcessed++;
}

return order;
}

/* A helper function to insert projects with zero dependencies into the order
* array, starting at index offset. */
int addNonDependent(Project[] order, Arraylist<Project> projects, int offset) {
for (Project project: projects) {
if (project.getNumberDependencies() == 0) {
order[offset] = project;
offset++;
}
}
return offset;
}

public class Graph {
private Arraylist<Project> nodes= new Arraylist<Project>();
private HashMap<String, Project> map = new HashMap<String, Project>();

public Project getOrCreateNode(String name) {
if (!map.containsKey(name)) {
Project node = new Project(name);
map.put(name, node);
}

return map.get(name);
}

public void addEdge(String startName, String endName) {
Project start = getOrCreateNode(startName);
Project end= getOrCreateNode(endName);
}

public Arraylist<Project> getNodes() {
return nodes;
}
}

public class Project {
private Arraylist<Project> children = new Arraylist<Project>();
private HashMap<String, Project> map= new HashMap<String, Project>();
private String name;
private int dependencies = 0;

public Project(String n) {
name n;
}

public void addNeighbor(Project node) {
if (!map.containsKey(node.getName())) {
map.put(node.getName(), node);
node.incrementDependencies();
}
}

public void incrementDependencies() {
dependencies++;
}
public void decrementDependencies() {
dependencies--;
}

public String getName() {
return name;
}
public Arraylist<Project> getChildren() {
return children;
}
public int getNumberDependencies() {
return dependencies;
}
}

Stack<Project> findBuildOrder(String[] projects, String[][] dependencies) {
Graph graph= buildGraph(projects, dependencies);
return orderProjects(graph.getNodes());
}

Stack<Project> orderProjects(ArrayList<Project> projects) {
Stack<Project> stack = new Stack<Project>();
for (Project project: projects) {
if (project.getState() == Project.State.BLANK) {
if (!doDFS(project, stack)) {
return null;
}
}
}
return stack;
}

boolean doDFS(Project project, Stack<Project> stack) {
if (project.getState() == Project.State.PARTIAL) {
return false; // Cycle
}

if (project.getState() == Project.State.BLANK) {
project.setState(Project.State.PARTIAL);
ArrayList<Project> children = project.getChildren();
for (Project child : children) {
if (!doDFS(child, stack)) {

}
return false;
}
project.setState(Project.State.COMPLETE);
stack.push(project);
}
return true;
}
/* Essentially equivalent to earlier solution, with state info added and
* dependency count removed. */
public class Project {
public enum State {COMPLETE, PARTIAL, BLANK};
private State state = State.BLANK;
public State getState() {
return state;
}
public void setState(State st) {
state = st;
}
/* Duplicate code removed for brevity*/
}