Problem Explanation

In this problem, we are asked to find out if it is possible to finish all the courses given certain prerequisites. The prerequisites are defined by pairs of courses, where to take the first course in the pair you must have finished the second course.

Formally the problem asks you to detect a cycle in a directed graph, where the nodes are courses and the edges are prerequisites. If there is a cycle, it means that there are circular prerequisites, or in other words, there are some courses that depend on each other and thus, it’s impossible to finish all the courses.

Let's walk through an example. Assume we have 4 courses labeled 0 to 3. The prerequisites are [[1,0],[2,1],[3,2]]. It means to take course 1 we must have finished course 0, and to take course 2 we should have finished course 1, and to take course 3 we should have finished course 2. This results in a sequence like this: 0 -> 1 -> 2 -> 3. Since there is no cycle in the sequence, it's possible to finish all the courses.

Solution Approach

A possible way to solve this problem is by using Depth-First Search (DFS) to find cycles in a directed graph. DFS is used for exploring or traversing tree or graph data structures. For a graph, DFS starts at a particular vertex and explores as far as possible along each branch before backtracking.

A node that is currently being explored is tagged as Visiting. If we encounter a node that is already in a Visiting state, it means we've found a loop, and it's impossible to finish the courses.

If no cycles detected, all nodes are finally tagged as Visited, and it's possible to finish all courses.

Now let's implement this in various programming languages.

Python Solution

1
2python
3class Solution:
4    def canFinish(self, numCourses, prerequisites):
5        graph = [[] for _ in range(numCourses)]
6        visited = [0 for _ in range(numCourses)]
7
8        # create graph
9        for pair in prerequisites:
10            x, y = pair
11            graph[x].append(y)
12
13        # visit each node
14        for i in range(numCourses):
15            if not self.dfs(graph, visited, i):
16                return False
17        return True
18
19    # use DFS to find if a cycle exists
20    def dfs(self, graph, visited, i):
21        # if ith node is marked as being visited, then a cycle is found
22        if visited[i] == -1:
23            return False
24        # if it is done visited, then do not visit again
25        if visited[i] == 1:
26            return True
27        # mark as being visited
28        visited[i] = -1
29        # visit all the neighbours
30        for j in graph[i]:
31            if not self.dfs(graph, visited, j):
32                return False
33        # after visit all the neighbours, mark it as done visited
34        visited[i] = 1
35        return True

Java Solution

1
2java 
3class Solution {
4    public boolean canFinish(int n, int[][] prerequisites) {
5        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
6        for(int i = 0; i < n; i++) {
7            graph.add(new ArrayList<Integer>());
8        }
9        
10        for(int[] courses : prerequisites) {
11            graph.get(courses[1]).add(courses[0]);
12        }
13        
14        int[] visited = new int[n];
15        for(int i = 0; i < n; i++) {
16            if(visited[i] == 0 && DFS(graph, visited, i)) {
17                return false;
18            }
19        }
20        
21        return true;
22    }
23    
24    private boolean DFS(ArrayList<ArrayList<Integer>> graph, int[] visited, int course) {
25        if(visited[course] == 1) {
26            return true;
27        }
28        if(visited[course] == -1) {
29            return false;
30        }
31        visited[course] = -1;
32        for(int nextCourse : graph.get(course)) {
33            if(!DFS(graph, visited, nextCourse)) { 
34              return false;
35            }
36        }
37        visited[course] = 1;
38        return true;
39    }
40}

JavaScript Solution

1
2javascript
3const canFinish = function(numCourses, prerequisites) {
4  const adjacencyList = new Map();
5  const seen = {};
6  const seeing = {};
7  
8  for (let [v, e] of prerequisites) {
9    if (adjacencyList.has(v)) {
10      adjacencyList.get(v).push(e);
11    } else {
12      adjacencyList.set(v, [e]);
13    }
14  }
15
16  for (let [v, edges] of adjacencyList) {
17    if (!DFS(v)) {
18      return false;
19    }
20  }
21
22  function DFS(v) {
23    if (seen[v]) return true;
24    if (seeing[v]) return false;
25
26    seeing[v] = true;
27    const edges = adjacencyList.get(v);
28    if (edges) {
29      for (let e of edges) {
30        if (!DFS(e)) {
31          return false;
32        }
33      }
34    }
35    seen[v] = true;
36    delete seeing[v];
37    return true;
38  }
39
40  return true;
41};

C++ Solution

1
2c++
3class Solution {
4public:
5    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
6        vector<vector<int>> graph(numCourses);
7        vector<int> degrees(numCourses,0);
8        for (int i = 0 ; i < prerequisites.size(); i++) {
9            graph[prerequisites[i][1]].push_back(prerequisites[i][0]);
10            degrees[prerequisites[i][0]]++;
11        }
12        queue<int> bfs;
13        for (int i = 0 ; i < numCourses; i++) {
14            if (degrees[i] == 0) {
15                bfs.push(i);
16            }
17        }
18        while (!bfs.empty()) {
19            int course = bfs.front();
20            bfs.pop();
21            for (int i = 0 ; i < graph[course].size(); i++) {
22                degrees[graph[course][i]]--;
23                if (degrees[graph[course][i]] == 0) {
24                    bfs.push(graph[course][i]);
25                }
26            }
27        }
28        for (int i = 0 ; i < numCourses; i++) {
29            if (degrees[i]!=0) return false;
30        }
31        return true; 
32    }
33};

C# Solution

1
2csharp
3public class Solution {
4    public bool CanFinish(int numCourses, int[][] prerequisites) {
5        List<int>[] graph = new List<int>[numCourses];
6        int[] indegree = new int[numCourses];
7        
8        for(int i = 0; i<numCourses; i++)
9            graph[i] = new List<int>();
10        
11        foreach(var prereq in prerequisites){
12            graph[prereq[1]].Add(prereq[0]);
13            indegree[prereq[0]]++;
14        }
15        
16        Queue<int> q = new Queue<int>();
17        for(int i = 0; i< numCourses; i++){
18            if(indegree[i] == 0)
19                q.Enqueue(i);
20        }
21        
22        while(q.Count != 0){
23            int course = q.Dequeue();
24            foreach(var e in graph[course]){
25                if(--indegree[e] == 0)
26                    q.Enqueue(e);
27            }
28        }
29        
30        for(int i = 0; i< numCourses; i++)
31            if(indegree[i] != 0)
32                return false;
33        
34        return true;
35    }
36}

Afterword

In this problem, we need to ensure that we are visiting nodes that have not been visited yet, identifying visiting nodes, and marking nodes that have been visited fully. This ensures we do not get stuck in an infinite loop and can detect cycles efficiently. Overall, the problem demonstrates how to conduct a Depth-First Search on a graph and detect cycles in the graph.## Swift Solution

1
2swift
3class Solution {
4    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
5        var graph = [[Int]](repeating: [Int](), count: numCourses)
6        var visited = [Int](repeating: 0, count: numCourses)
7        
8        for pair in prerequisites {
9            let x = pair[1]
10            let y = pair[0]
11            graph[x].append(y)
12        }
13        
14        for i in 0..<numCourses {
15            if !dfs(graph, &visited, i) {
16                return false
17            }
18        }
19        
20        return true
21    }
22    
23    private func dfs(_ graph: [[Int]], _ visited: inout [Int], _ i: Int) -> Bool {
24        if visited[i] == -1 {
25            return false
26        }
27        
28        if visited[i] == 1 {
29            return true
30        }
31        
32        visited[i] = -1
33        for j in graph[i] {
34            if !dfs(graph, &visited, j) {
35                return false
36            }
37        }
38        visited[i] = 1
39        return true
40    }
41}

Kotlin Solution

1
2kotlin
3class Solution {
4    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
5        val graph = Array<ArrayList<Int>>(numCourses) { ArrayList() }
6        val visited = IntArray(numCourses)
7        
8        for (pair in prerequisites) {
9            graph[pair[1]].add(pair[0])
10        }
11        
12        for (i in 0 until numCourses) {
13            if (!dfs(i, graph, visited)) {
14                return false
15            }
16        }
17        return true
18    }
19    
20    private fun dfs(currCourse: Int, graph: Array<ArrayList<Int>>, visited: IntArray): Boolean {
21        
22        if (visited[currCourse] == -1) {
23            return false
24        } else if (visited[currCourse] == 1) {
25            return true
26        }
27
28        visited[currCourse] = -1
29        for (nextCourse in graph[currCourse]) {
30            if (!dfs(nextCourse, graph, visited)) {
31                return false
32            }
33        }
34        
35        visited[currCourse] = 1
36        return true
37    }
38}

PHP Solution

1
2php
3class Solution {
4
5    /**
6     * @param Integer $numCourses
7     * @param Integer[][] $prerequisites
8     * @return Boolean
9     */
10    function canFinish($numCourses, $prerequisites) {
11        $graph = array_fill(0, $numCourses, []);
12        $visited = array_fill(0, $numCourses, 0);
13
14        foreach ($prerequisites as $pair) {
15            $x = $pair[0];
16            $y = $pair[1];
17            $graph[$x][] = $y;
18        }
19
20        for ($i = 0; $i < $numCourses; $i++) {
21            if (!self::dfs($graph, $visited, $i)) {
22                return false;
23            }
24        }
25        return true;
26    }
27
28    static function dfs($graph, &$visited, $i) {
29        if ($visited[$i] == -1) return false;
30        if ($visited[$i] == 1) return true;
31        $visited[$i] = -1;
32        foreach ($graph[$i] as $j) {
33            if (!self::dfs($graph, $visited, $j)) {
34                return false;
35            }
36        }
37        $visited[$i] = 1;
38        return true;
39    }
40}
41

Conclusion

Going through the problem, you can see that it revolves around a simple concept of detecting a cycle in a directed graph. The solutions shared above are easy to understand and implement, and are also optimised to work for larger data sets. Learning how to solve problems like this one is very useful, especially for coding interviews, because it not only tests your programming abilities but also your ability to apply algorithms for a large range of problems.