207. Course Schedule

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?

Constraints

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

• You may assume that there are no duplicate edges in the input prerequisites.

• 1 <= numCourses <= 10^5

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList();
        
        for(int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<Integer>());
        }
        
        for(int[] pre: prerequisites) {
            adjList.get(pre[1]).add(pre[0]);
        }
        
        boolean[] isProcessing = new boolean[numCourses];
        boolean[] isProcessed = new boolean[numCourses];
        
        for(int i = 0; i < numCourses; i++) {
            if(isCycleExist(i, adjList, isProcessing, isProcessed)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean isCycleExist(int u,
                                 List<List<Integer>> adjList, 
                                 boolean[] isProcessing,
                                 boolean[] isProcessed) {
        if(isProcessed[u]) return false;
        
        if(isProcessing[u]) return true;
        
        isProcessing[u] = true;
        
        for(int v: adjList.get(u)) {
            if(isCycleExist(v, adjList, isProcessing, isProcessed)) {
                return true;
            }
        }
        
        isProcessing[u] = false;
        isProcessed[u] = true;
        
        return false;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] courses = new ArrayList[numCourses];
        
        for(int i = 0; i < numCourses; i++) {
            courses[i] = new ArrayList<Integer>();
        }
        
        for(int[] pre: prerequisites) {
            courses[pre[1]].add(pre[0]);
        }
        
        boolean[] isProcessing = new boolean[numCourses];
        boolean[] isProcessed = new boolean[numCourses];
        
        for(int i = 0; i < numCourses; i++) {
            if(isCycleExist(i, courses, isProcessing, isProcessed)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean isCycleExist(int u,
                                 ArrayList[] courses, 
                                 boolean[] isProcessing,
                                 boolean[] isProcessed) {
        if(isProcessed[u]) return false;
        
        if(isProcessing[u]) return true;
        
        isProcessing[u] = true;
        
        ArrayList<Integer> course = courses[u];
        for(int v = 0; v < course.size(); v++) {
            if(isCycleExist((int)course.get(v), courses, isProcessing, isProcessed)) {
                return true;
            }
        }
        
        isProcessing[u] = false;
        isProcessed[u] = true;
        
        return false;
    }
}

Follow up