My solution for leetcode problem called course schedule (problem no.207)
Depth first search Approach:
- Build adjacency list
- Perform depth first search on each node and check if cycle is found
- Within dfs for each node,
- Check if already marked as visiting (-1) return false
- Check if visited in another iteration (1) return true
- If not, perform dfs on subsequent course nodes
- Reset to 1, to indicate visited nodes
- Return result
Solution:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) { if(numCourses <= 1) return true; // build adjacency list Map<Integer, List<Integer>> map = new HashMap<>(); for(int[] p: prerequisites) { if(!map.containsKey(p[1])) map.put(p[1], new ArrayList<Integer>()); map.get(p[1]).add(p[0]); } int[] visited = new int[numCourses]; // perform dfs for each node for(int i = 0; i < numCourses; i++) { if(!dfs(map, i, visited)) return false; } // return result return true; } private boolean dfs(Map<Integer,List<Integer>> map, int index, int[] visited) { if(visited[index] == -1) return false; if(visited[index] == 1) return true; visited[index] = -1; if(map.containsKey(index)) { for(int j: map.get(index)) { if(!dfs(map, j, visited)) return false; visited[j] = 1; } } visited[index] = 1; return true; } }
Time complexity:
In worst case, will iterate through the entire graph once, so O(V + E) where V is number of vertices and E is number of edges in the graph
Space complexity:
Because the adjacency list is built, O(V + E) where V is number of vertices and E is number of edges in the graph
Comments
Post a Comment