Skip to main content

207. Course Schedule

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

Popular posts from this blog