Massive Algorithms: LeetCode 207

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<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //store courses that have no prerequisites
    LinkedList<Integer> queue = new LinkedList<Integer>();
    for(int i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.add(i);
        }
    }
 
    // number of courses that have no prerequisites
    int numNoPre = queue.size();
 
    while(!queue.isEmpty()){
        int top = queue.remove();
        for(int i=0; i<len; i++){
            // if a course's prerequisite can be satisfied by a course in queue
            if(prerequisites[i][1]==top){//not efficient
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    numNoPre++;
                    queue.add(prerequisites[i][0]);
                }
            }
        }
    }
 
    return numNoPre == numCourses;
}

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)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
    
    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;
        }
        list.add(readyCourse);
        indegree[readyCourse]++;
    }
    
    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>());            
            neighbors.get(edges[i][1]).add(edges[i][0]);
        }

        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;     

    curPath.add(kid);
    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<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>();
    for(int[] a: prerequisites){
        if(map.containsKey(a[1])){
            map.get(a[1]).add(a[0]);
        }else{
            ArrayList<Integer> l = new ArrayList<Integer>();
            l.add(a[0]);
            map.put(a[1], l);
        }
    }
 
    for(int i=0; i<numCourses; i++){
        if(!canFinishDFS(map, visit, i))
            return false;
    }
 
    return true;
}
 
private boolean canFinishDFS(HashMap<Integer,ArrayList<Integer>> 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;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     for (int v=0; v<V; v++)  
       if(!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle);  
     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
这个题目很容易分析出来是check if a directed graph has a cycle.

但是给的graph是 a list of edges，如果只给定一些edges我们是无法对graph进行遍历的，所以我们可以建立一个adjacent list, 并且带上一个state记录每个node的状态。

这个题目里面的adjacent list 可以用map来做，然后对map做DFS遍历。
采用的是DFS + mark visitIII -> 3 states
但是需要注意的是，需要对graph里面的每个Node进行遍历，才能遍历到所有的可能。
这个题目里面没有 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++) {
G.addEdge(prerequisites[i][j], prerequisites[i][++j]);
}
}
DirectedCycle dag = new DirectedCycle(G);
return !dag.hasCycle();
}
判断有向图中是否有环

用一个数组boolean[] onStack保存递归调用期间栈上的所有顶点.

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

在递归执行dfs的过程中，记录当前下当前顶点在递归调用栈中，这样以后的递归调用栈只要判断它的相连点是否在之前的递归调用栈中出现过，就能判断是否有环。
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;
private ArrayList<Integer>[] adj;
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) {
adj[v].add(w);
}
public int V() {
return V;
}
public Iterable<Integer> adj(int v) {
return adj[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:
https://leetcode.com/discuss/35035/oo-easy-to-read-java-solution

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];

graph.addEdge(first, second);

}

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);

nodes.add(node);

map.put(name, node);

}

return map.get(name);

}

public void addEdge(String startName, String endName) {

Project start = getOrCreateNode(startName);

Project end= getOrCreateNode(endName);

start.addNeighbor(end);

}

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())) {

children.add(node);

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*/
}

LeetCode 207 - Course Schedule I

Labels

Popular Posts