How to Check if it’s Possible to Finish all the Course (Leetcode 207)

  • Post last modified:July 16, 2022
  • Reading time:5 mins read

Introduction

In this article, we will solve Leetcode problem 207 which help us to learn about graph data structure and operating DFS on graph data structure.

Problem Statement

We have given a number of courses that we have to take ( 0 -> n-1 ) and we have been also given prerequisites that indicate a number of courses that we must take before that.

We have to check if we can finish all the courses or not. if we can then we should return true otherwise we need to return false.

Example #1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0.
So it is possible

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.

Thinking about Solution

Since we have been given course and dependency, the first thing we can do is to create a map which is made up of course as key and value as dependency list of course that we need to take first.

We can initialize this map by traversing the prerequisite list that has been given to us in the example.

Once we have the map, we can iterate over it, and for each course, we can traverse the dependent course and check if that course can be taken. It sounds like executing a depth-first search for the given course as a node.

Solution

  • Below solution we have initialized map with course as key and dependent course (List of courses) as value.
  • We can traverse the map and take each course. If we have visited this course before then we detected a cycle. Consider a case where we have course 1 -> 0 and 0-> 1, in that case, we will be trapped in cycle, so in order to detect that we need to create a set and add all the visited in our dfs to cycle .
  • If the given course is not in the cycle then we can check if this course has been taken previously or not. for instance consider a case, where we 1-> 0, 0-> 2, in this case, we can take course 1. Now for another course 5 -> 1, we don’t have to traverse 1 again we can just add all the courses that can be taken to the visited set to that we can just return the result and optimize our solution.
  • If the course is not already in the visited set then, first we should add it to our cycle set to avoid cycle for future dfs call, after that, we can get the dependency list of the courses and and run dfs on each dependent course. If any of the dependent courses cannot be taken then we can say that we cannot take the course.
  • Since we have already executed the dfs for the given course, now we can remove it from the cycle and add it to visited set.
  • Finally, we can return true as we can complete this course since we have encountered any cyclic dependency for a given course.
class Solution {
    // create a set to store all the courses that has been visited
    HashSet<Integer> visit = new HashSet<>();

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // course map that creates map of course -> dependend_course
        Map<Integer,List<Integer>> courseMap = new HashMap<>();
        HashSet<Integer> cycle = new HashSet<>();
        for(int i=0;i<numCourses;i++){
            courseMap.put(i, new ArrayList<>());
        }
        // iterating for each course
        for(int i=0;i<prerequisites.length;i++){
             List<Integer> list = courseMap.get(prerequisites[i][0]);
             list.add((prerequisites[i][1]));
             courseMap.put(prerequisites[i][0], list);
         }
        
    //    courseMap.entrySet().stream().forEach(a-> System.out.println(a.getKey()+", "+a.getValue()));
        
        for(int i=0;i<numCourses;i++){
            if(!dfs(courseMap, i, visited)){
                return false;
            }
        }
        
        return true;
    }
    
    
    private boolean dfs(Map<Integer,List<Integer>> courseMap, int course, HashSet<Integer> cycle){
        // if there is cyclic dependency then return false since we cannot 
        // finish course 
        if(cycle.contains(course)){
            return false;
        }
        // if this course has been visited previously then we dont need to 
        // visit it again and just return simply true
        if(visit.contains(course)){
            return true;
        }
        // if first visit then add to cycle set so that we can detect it
        cycle.add(course);
        // get the list of dependency of for current course
        List<Integer> courses = courseMap.get(course);
        // iterate over each dependent course and run dfs over it
        for(Integer c:courses){
       // if any of the dependent course cannot be taken then return false
             if(!dfs(courseMap, c, visited)){ 
                 return false;
             }
        }
        // since we have checked for given course and checked its 
        // dependent course, we can remove it from cycle set 
        cycle.remove(course);
        // add to visit set so that we dont have to check again
        visit.add(course);
        return true;
    }
}

Result

Our result takes 13 ms to execute and beats 28% of the java solutions.
Since this problem is solved using graph data structure hence our Time complexity and Space complexity would be that of graph
TC: O(Vertices + Edges), for traversing each vertex and its adjacency list of dependent courses.
SC: O(Vertices) since we are storing at max V number of courses in our map/set.

Conclusion

In this article, we solve Leetcode problem number 207. This problem requires us to use graph data structure and operate DFS on it.

Leave a Reply