207. Course Schedule - Explanation

Description

You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

The pair [0, 1], indicates that must take course 1 before taking course 0.

There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.

Return true if it is possible to finish all courses, otherwise return false.

Example 1:

Input: numCourses = 2, prerequisites = [[0,1]]

Output: true

Explanation: First take course 1 (no prerequisites) and then take course 0.

Example 2:

Input: numCourses = 2, prerequisites = [[0,1],[1,0]]

Output: false

Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.

Constraints:

1 <= numCourses <= 1000
0 <= prerequisites.length <= 1000
prerequisites[i].length == 2
0 <= a[i], b[i] < numCourses
All prerequisite pairs are unique.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(V + E) time and O(V + E) space, where V is the number of courses (nodes) and E is the number of prerequisites (edges).

Hint 1

Consider the problem as a graph where courses represent the nodes, and prerequisite[i] = [a, b] represents a directed edge from a to b. We need to determine whether the graph contains a cycle. Why? Because if there is a cycle, it is impossible to complete the courses involved in the cycle. Can you think of an algorithm to detect cycle in a graph?

Hint 2

We can use the Depth First Search (DFS) algorithm to detect a cycle in a graph. We iterate over each course, run a DFS from that course, and first try to finish its prerequisite courses by recursively traversing through them. To detect a cycle, we initialize a hash set called path, which contains the nodes visited in the current DFS call. If we encounter a course that is already in the path, we can conclude that a cycle is detected. How would you implement it?

Hint 3

We run a DFS starting from each course by initializing a hash set, path, to track the nodes in the current DFS call. At each step of the DFS, we return false if the current node is already in the path, indicating a cycle. We recursively traverse the neighbors of the current node, and if any of the neighbor DFS calls detect a cycle, we immediately return false. Additionally, we clear the neighbors list of a node when no cycle is found from that node to avoid revisiting those paths again.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation - Building adjacency lists from edge pairs to represent directed graphs
Depth-First Search (DFS) - Recursive graph traversal for exploring dependencies and detecting cycles
Topological Sort (Kahn's Algorithm) - BFS-based approach using indegree to determine if a valid ordering exists
Cycle Detection - Tracking nodes in the current recursion path to identify back edges indicating cycles

1. Cycle Detection (DFS)

Intuition

Each course is a node, and each prerequisite is a directed edge.
You can finish all courses only if there is no cycle in this directed graph.

A cycle means:

Course A needs B
B needs C
C needs A
So you’re stuck forever.

We use DFS with cycle detection:

While doing DFS, keep track of courses in the current recursion path.
If we visit a course already in the current path → cycle found.
If a course has no prerequisites left, it’s safe.

Algorithm

Build a graph where each course points to its prerequisites.
Use a visiting set to track the current DFS path.
For each course:
- Run DFS.
- If the course is already in visiting, return false (cycle).
- Recursively DFS its prerequisites.
After successfully processing a course, clear its prerequisite list (mark as done).
If all courses are processed without cycles, return true.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Map each course to its prerequisites
        preMap = {i: [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        # Store all courses along the current DFS path
        visiting = set()

        def dfs(crs):
            if crs in visiting:
                # Cycle detected
                return False
            if preMap[crs] == []:
                return True

            visiting.add(crs)
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False
            visiting.remove(crs)
            preMap[crs] = []
            return True

        for c in range(numCourses):
            if not dfs(c):
                return False
        return True

public class Solution {
    // Map each course to its prerequisites
    private Map<Integer, List<Integer>> preMap = new HashMap<>();
    // Store all courses along the current DFS path
    private Set<Integer> visiting = new HashSet<>();

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        for (int i = 0; i < numCourses; i++) {
            preMap.put(i, new ArrayList<>());
        }
        for (int[] prereq : prerequisites) {
            preMap.get(prereq[0]).add(prereq[1]);
        }

        for (int c = 0; c < numCourses; c++) {
            if (!dfs(c)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int crs) {
        if (visiting.contains(crs)) {
            // Cycle detected
            return false;
        }
        if (preMap.get(crs).isEmpty()) {
            return true;
        }

        visiting.add(crs);
        for (int pre : preMap.get(crs)) {
            if (!dfs(pre)) {
                return false;
            }
        }
        visiting.remove(crs);
        preMap.put(crs, new ArrayList<>());
        return true;
    }
}

class Solution {
    // Map each course to its prerequisites
    unordered_map<int, vector<int>> preMap;
    // Store all courses along the current DFS path
    unordered_set<int> visiting;

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for (int i = 0; i < numCourses; i++) {
            preMap[i] = {};
        }
        for (const auto& prereq : prerequisites) {
            preMap[prereq[0]].push_back(prereq[1]);
        }

        for (int c = 0; c < numCourses; c++) {
            if (!dfs(c)) {
                return false;
            }
        }
        return true;
    }

    bool dfs(int crs) {
        if (visiting.count(crs)) {
            // Cycle detected
            return false;
        }
        if (preMap[crs].empty()) {
            return true;
        }

        visiting.insert(crs);
        for (int pre : preMap[crs]) {
            if (!dfs(pre)) {
                return false;
            }
        }
        visiting.erase(crs);
        preMap[crs].clear();
        return true;
    }
};

class Solution {
    /**
     * @param {number} numCourses
     * @param {number[][]} prerequisites
     * @return {boolean}
     */
    canFinish(numCourses, prerequisites) {
        const preMap = new Map();
        for (let i = 0; i < numCourses; i++) {
            preMap.set(i, []);
        }
        for (let [crs, pre] of prerequisites) {
            preMap.get(crs).push(pre);
        }

        // Store all courses along the current DFS path
        const visiting = new Set();

        const dfs = (crs) => {
            if (visiting.has(crs)) {
                // Cycle detected
                return false;
            }
            if (preMap.get(crs).length === 0) {
                return true;
            }

            visiting.add(crs);
            for (let pre of preMap.get(crs)) {
                if (!dfs(pre)) {
                    return false;
                }
            }
            visiting.delete(crs);
            preMap.set(crs, []);
            return true;
        };

        for (let c = 0; c < numCourses; c++) {
            if (!dfs(c)) {
                return false;
            }
        }
        return true;
    }
}

public class Solution {
    // Map each course to its prerequisites
    private Dictionary<int, List<int>> preMap = new Dictionary<int, List<int>>();
    // Store all courses along the current DFS path
    private HashSet<int> visiting = new HashSet<int>();

    public bool CanFinish(int numCourses, int[][] prerequisites) {
        for (int i = 0; i < numCourses; i++) {
            preMap[i] = new List<int>();
        }
        foreach (var prereq in prerequisites) {
            preMap[prereq[0]].Add(prereq[1]);
        }

        for (int c = 0; c < numCourses; c++) {
            if (!Dfs(c)) {
                return false;
            }
        }
        return true;
    }

    private bool Dfs(int crs) {
        if (visiting.Contains(crs)) {
            // Cycle detected
            return false;
        }
        if (preMap[crs].Count == 0) {
            return true;
        }

        visiting.Add(crs);
        foreach (int pre in preMap[crs]) {
            if (!Dfs(pre)) {
                return false;
            }
        }
        visiting.Remove(crs);
        preMap[crs].Clear();
        return true;
    }
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    // Map each course to its prerequisites
    preMap := make(map[int][]int)
    for i := 0; i < numCourses; i++ {
        preMap[i] = []int{}
    }
    for _, prereq := range prerequisites {
        crs, pre := prereq[0], prereq[1]
        preMap[crs] = append(preMap[crs], pre)
    }

    // Store all courses along the current DFS path
    visiting := make(map[int]bool)

    var dfs func(int) bool
    dfs = func(crs int) bool {
        if visiting[crs] {
            // Cycle detected
            return false
        }
        if len(preMap[crs]) == 0 {
            return true
        }

        visiting[crs] = true
        for _, pre := range preMap[crs] {
            if !dfs(pre) {
                return false
            }
        }
        visiting[crs] = false
        preMap[crs] = []int{}
        return true
    }

    for c := 0; c < numCourses; c++ {
        if !dfs(c) {
            return false
        }
    }
    return true
}

class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        // Map each course to its prerequisites
        val preMap = HashMap<Int, MutableList<Int>>()
        for (i in 0 until numCourses) {
            preMap[i] = mutableListOf()
        }
        for (prereq in prerequisites) {
            val (crs, pre) = prereq
            preMap[crs]!!.add(pre)
        }

        // Store all courses along the current DFS path
        val visiting = HashSet<Int>()

        fun dfs(crs: Int): Boolean {
            if (crs in visiting) {
                // Cycle detected
                return false
            }
            if (preMap[crs]!!.isEmpty()) {
                return true
            }

            visiting.add(crs)
            for (pre in preMap[crs]!!) {
                if (!dfs(pre)) {
                    return false
                }
            }
            visiting.remove(crs)
            preMap[crs] = mutableListOf()
            return true
        }

        for (c in 0 until numCourses) {
            if (!dfs(c)) {
                return false
            }
        }
        return true
    }
}

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        // Map each course to its prerequisites
        var preMap = [Int: [Int]]()
        for i in 0..<numCourses {
            preMap[i] = []
        }
        for pair in prerequisites {
            preMap[pair[0]]!.append(pair[1])
        }

        // Store all courses along the current DFS path
        var visiting = Set<Int>()

        func dfs(_ crs: Int) -> Bool {
            if visiting.contains(crs) {
                // Cycle detected
                return false
            }
            if preMap[crs]!.isEmpty {
                return true
            }

            visiting.insert(crs)
            for pre in preMap[crs]! {
                if !dfs(pre) {
                    return false
                }
            }
            visiting.remove(crs)
            preMap[crs] = []
            return true
        }

        for c in 0..<numCourses {
            if !dfs(c) {
                return false
            }
        }
        return true
    }
}

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut pre_map = vec![vec![]; n];
        for pair in &prerequisites {
            pre_map[pair[0] as usize].push(pair[1] as usize);
        }

        let mut visiting = vec![false; n];

        fn dfs(crs: usize, pre_map: &mut Vec<Vec<usize>>, visiting: &mut Vec<bool>) -> bool {
            if visiting[crs] {
                return false;
            }
            if pre_map[crs].is_empty() {
                return true;
            }

            visiting[crs] = true;
            let prereqs: Vec<usize> = pre_map[crs].clone();
            for pre in prereqs {
                if !dfs(pre, pre_map, visiting) {
                    return false;
                }
            }
            visiting[crs] = false;
            pre_map[crs].clear();
            true
        }

        for c in 0..n {
            if !dfs(c, &mut pre_map, &mut visiting) {
                return false;
            }
        }
        true
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of courses and $E$ is the number of prerequisites.

2. Topological Sort (Kahn's Algorithm)

Intuition

Treat each course as a node and each prerequisite as a directed edge.
If a course has no prerequisites, it can be taken immediately.

Kahn's Algorithm repeatedly takes courses that have zero prerequisites.
When we finish a course, we remove its dependency effect from other courses.

If all courses can be taken this way - no cycle, return true
If some courses are never taken - cycle exists, return false

Algorithm

Build a graph and compute indegree (number of prerequisites) for each course.
Add all courses with indegree = 0 into a queue.
While the queue is not empty:
- Remove a course from the queue.
- Mark it as finished.
- Reduce the indegree of its dependent courses.
- If any dependent course reaches indegree = 0, add it to the queue.
After processing:
- If finished courses == total courses - return true
- Else - return false

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        adj = [[] for i in range(numCourses)]
        for src, dst in prerequisites:
            indegree[dst] += 1
            adj[src].append(dst)

        q = deque()
        for n in range(numCourses):
            if indegree[n] == 0:
                q.append(n)

        finish = 0
        while q:
            node = q.popleft()
            finish += 1
            for nei in adj[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)

        return finish == numCourses

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            indegree[pre[1]]++;
            adj.get(pre[0]).add(pre[1]);
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }

        int finish = 0;
        while (!q.isEmpty()) {
            int node = q.poll();
            finish++;
            for (int nei : adj.get(node)) {
                indegree[nei]--;
                if (indegree[nei] == 0) {
                    q.add(nei);
                }
            }
        }

        return finish == numCourses;
    }
}

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
        vector<vector<int>> adj(numCourses);

        for (auto& pre : prerequisites) {
            indegree[pre[1]]++;
            adj[pre[0]].push_back(pre[1]);
        }

        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int finish = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            finish++;
            for (int nei : adj[node]) {
                indegree[nei]--;
                if (indegree[nei] == 0) {
                    q.push(nei);
                }
            }
        }

        return finish == numCourses;
    }
};

class Solution {
    /**
     * @param {number} numCourses
     * @param {number[][]} prerequisites
     * @return {boolean}
     */
    canFinish(numCourses, prerequisites) {
        let indegree = Array(numCourses).fill(0);
        let adj = Array.from({ length: numCourses }, () => []);
        for (let [src, dst] of prerequisites) {
            indegree[dst]++;
            adj[src].push(dst);
        }

        let q = new Queue();
        for (let i = 0; i < numCourses; i++) {
            if (indegree[i] === 0) {
                q.push(i);
            }
        }

        let finish = 0;
        while (!q.isEmpty()) {
            let node = q.pop();
            finish++;
            for (let nei of adj[node]) {
                indegree[nei]--;
                if (indegree[nei] === 0) {
                    q.push(nei);
                }
            }
        }

        return finish === numCourses;
    }
}

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<int>> adj = new List<List<int>>();
        for (int i = 0; i < numCourses; i++) {
            adj.Add(new List<int>());
        }
        foreach (var pre in prerequisites) {
            indegree[pre[1]]++;
            adj[pre[0]].Add(pre[1]);
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.Enqueue(i);
            }
        }

        int finish = 0;
        while (q.Count > 0) {
            int node = q.Dequeue();
            finish++;
            foreach (var nei in adj[node]) {
                indegree[nei]--;
                if (indegree[nei] == 0) {
                    q.Enqueue(nei);
                }
            }
        }

        return finish == numCourses;
    }
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    indegree := make([]int, numCourses)
    adj := make([][]int, numCourses)
    for i := 0; i < numCourses; i++ {
        adj[i] = []int{}
    }

    for _, prereq := range prerequisites {
        src, dst := prereq[0], prereq[1]
        indegree[dst]++
        adj[src] = append(adj[src], dst)
    }

    q := []int{}
    for n := 0; n < numCourses; n++ {
        if indegree[n] == 0 {
            q = append(q, n)
        }
    }

    finish := 0
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        finish++
        for _, nei := range adj[node] {
            indegree[nei]--
            if indegree[nei] == 0 {
                q = append(q, nei)
            }
        }
    }

    return finish == numCourses
}

class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        val indegree = IntArray(numCourses) { 0 }
        val adj = Array(numCourses) { mutableListOf<Int>() }

        for (prereq in prerequisites) {
            val (src, dst) = prereq
            indegree[dst]++
            adj[src].add(dst)
        }

        val q: Queue<Int> = LinkedList()
        for (n in 0 until numCourses) {
            if (indegree[n] == 0) {
                q.add(n)
            }
        }

        var finish = 0
        while (q.isNotEmpty()) {
            val node = q.poll()
            finish++
            for (nei in adj[node]) {
                indegree[nei]--
                if (indegree[nei] == 0) {
                    q.add(nei)
                }
            }
        }

        return finish == numCourses
    }
}

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var indegree = Array(repeating: 0, count: numCourses)
        var adj = Array(repeating: [Int](), count: numCourses)

        for pair in prerequisites {
            let src = pair[0]
            let dst = pair[1]
            indegree[dst] += 1
            adj[src].append(dst)
        }

        var queue = Deque<Int>()
        for n in 0..<numCourses {
            if indegree[n] == 0 {
                queue.append(n)
            }
        }

        var finish = 0
        while !queue.isEmpty {
            let node = queue.popFirst()!
            finish += 1
            for nei in adj[node] {
                indegree[nei] -= 1
                if indegree[nei] == 0 {
                    queue.append(nei)
                }
            }
        }

        return finish == numCourses
    }
}

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut indegree = vec![0i32; n];
        let mut adj = vec![vec![]; n];

        for pre in &prerequisites {
            let (src, dst) = (pre[0] as usize, pre[1] as usize);
            indegree[dst] += 1;
            adj[src].push(dst);
        }

        let mut queue = VecDeque::new();
        for i in 0..n {
            if indegree[i] == 0 {
                queue.push_back(i);
            }
        }

        let mut finish = 0;
        while let Some(node) = queue.pop_front() {
            finish += 1;
            for &nei in &adj[node] {
                indegree[nei] -= 1;
                if indegree[nei] == 0 {
                    queue.push_back(nei);
                }
            }
        }

        finish == n
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of courses and $E$ is the number of prerequisites.

Common Pitfalls

Using a Single Visited Set Instead of Tracking the Current Path

A single visited set marks nodes as seen globally, but cycle detection requires knowing if a node is in the current DFS path. Without tracking the recursion path separately, you may miss cycles or falsely detect them.

# Wrong: single visited set
visited = set()
def dfs(node):
    if node in visited:
        return False  # This doesn't distinguish "finished" from "in current path"
    visited.add(node)
    for nei in adj[node]:
        if not dfs(nei):
            return False
    return True

# Correct: track visiting (current path) and visited (finished)
visiting = set()
def dfs(node):
    if node in visiting:
        return False  # Cycle: node is in current recursion path
    if preMap[node] == []:
        return True   # Already processed, no cycle
    visiting.add(node)
    for nei in preMap[node]:
        if not dfs(nei):
            return False
    visiting.remove(node)
    preMap[node] = []  # Mark as processed
    return True

Forgetting to Handle Disconnected Components

If you only start DFS from one node, you may miss cycles in disconnected parts of the graph. Always iterate through all courses and run DFS from each unvisited node.

# Wrong: only check from course 0
return dfs(0)

# Correct: check all courses
for c in range(numCourses):
    if not dfs(c):
        return False
return True

Incorrectly Building the Adjacency List

The prerequisite [a, b] means "to take course a, you must first take course b". Mixing up which course maps to which leads to checking the wrong dependencies and missing or falsely reporting cycles.