207. Course Schedule - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

Given numCourses labeled from 0 to numCourses-1 and a list of prerequisite pairs, determine if it’s possible to finish all courses. Each pair [a, b] in the prerequisites means course a depends on course b (i.e. you must take b before a). The task is to return true if all courses can be completed, or false if there is a cycle preventing completion.

Example 1:

Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Explanation: You can take course 0 first (no prerequisites), then take course 1 which depends on 0. This ordering completes all courses.

Example 2:

Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Explanation: The prerequisites form a cycle: 1 → 0 → 1. Course 1 depends on 0 and vice versa, creating an impossible situation where neither can be taken first. Therefore, it’s impossible to finish both courses.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
Each prerequisite pair has length 2.
0 <= ai, bi < numCourses
All prerequisite pairs are distinct (no duplicates).

Hints:

Graph Model: We can model the courses and their prerequisites as a directed graph. Each course is a node, and a directed edge bi -> ai indicates course bi must be taken before course ai (i.e. ai depends on bi). This forms a graph of course dependencies.
Cycle Detection: If there is a cycle in this directed graph, it means there’s a circular dependency (e.g. A depends on B, and B depends on A). In such cases, it’s impossible to complete all courses, because no valid ordering can satisfy the prerequisites. We should detect if a cycle exists in the graph.
Topological Sorting: If the graph has no cycles, we can find a topological order of courses (an ordering of nodes such that each prerequisite comes before the courses that depend on it). A topological ordering represents a valid course schedule. Essentially, the problem reduces to checking if a topological sort is possible. If yes, return true; if not (graph contains a cycle), return false.
Graph Representation: It’s convenient to use an adjacency list to represent the graph. For each course, keep a list of courses that depend on it. This way, given a course, you can quickly look up all subsequent courses that require it as a prerequisite.
Approaches: Two common strategies to solve this are:
1. BFS (Kahn’s Algorithm): Perform a breadth-first traversal using indegree counts (number of prerequisites) to detect if all courses can be taken in order.
2. DFS (Depth-First Search): Recursively traverse the graph and use cycle-detection (with recursion stack or color marking) to see if any cycle exists.

Approach 1: BFS (Topological Sort using Kahn’s Algorithm)

Idea: Use Kahn’s algorithm for topological sorting. This algorithm repeatedly picks courses with no remaining prerequisites and adds them to the order. By counting how many courses we can take, we can determine if all courses can be completed. If we end up processing all numCourses in this manner, it means we found a valid ordering (no cycle); if some courses remain unprocessed (indicating a cycle of dependencies), then it’s impossible to finish all courses.

Steps:

Build the Graph & Indegree Array: Create an adjacency list for the graph where each course maps to the list of courses that depend on it. Also initialize an indegree array to count the number of prerequisites (incoming edges) for each course. For each prerequisite pair [a, b], add an edge b -> a in the adjacency list and increment indegree[a] (since a has one more prerequisite, b). Courses with indegree = 0 have no prerequisites and can be taken first.
Initialize BFS Queue: Find all courses with no prerequisites (indegree 0) and put them into a queue (these are the courses we can take immediately). These form the starting points for our BFS.
Process Courses in Order: While the queue is not empty, do the following:
- Dequeue a course c and “take” it (add it to the order or count it as completed).
- For each neighbor course n in the adjacency list of c (i.e. courses that depend on c), reduce their indegree by 1 (since c is now taken, one prerequisite is satisfied).
- If any neighbor’s indegree becomes 0, it means all its prerequisites are now satisfied, so add that neighbor to the queue to be taken next.
- Continue until the queue is empty.
Check Completion: Keep a count of how many courses have been “taken” (dequeued from the queue). If this count equals numCourses by the end, then we have managed to take all courses in some order — return true. If there are still courses left unprocessed (count < numCourses), that means there was a cycle preventing some courses from ever having indegree 0; in this case return false (not all courses can be completed).

Using this approach, if a cycle exists, the BFS will terminate with some courses never reaching indegree 0 (the queue becomes empty early). If no cycle exists, we will eventually process all courses. This method effectively detects a cycle by checking if we could not take all courses by the end.

Python – BFS Approach (Kahn’s Algorithm):

Python3

. . . .

Explanation: We use an adjacency list graph to store edges from each course to the courses that depend on it, and an indegree list to count prerequisites for each course. We enqueue all courses with no prerequisites initially, then repeatedly take courses from the queue and decrement indegrees of their dependents. If a dependent’s indegree drops to 0, it becomes eligible to take and is added to the queue. Finally, if we have taken (taken_count) all numCourses, it means we found an order to finish all courses (return True); if not, some courses were never reachable (cycle present, return False).

Java – BFS Approach (Kahn’s Algorithm):

Java

. . . .

Explanation: We use an ArrayList of lists to represent the graph, and an indegree array for prerequisites count. We enqueue all initial courses with no prerequisites, then process each course from the queue, decrementing the indegree of adjacent (dependent) courses. If a dependent’s indegree becomes zero, we add it to the queue. In the end, we check if we have processed (takenCount) all the courses. If yes, return true; if not, it means some courses couldn’t be taken due to a cycle (return false).

Approach 2: DFS (Depth-First Search with Cycle Detection)

Idea: Use Depth-First Search to traverse the graph and detect cycles. We perform a DFS from each course that hasn’t been visited yet. While doing so, we maintain markers to distinguish between courses that are in the current recursion stack (being visited) and those that are already fully completed. If during DFS we try to visit a course that is currently in the recursion stack, it means we found a cycle (back-edge). If we finish DFS without encountering a cycle for all components of the graph, then all courses can be completed.

Steps:

Build the Graph: Same as in BFS, build an adjacency list representation of the directed graph of prerequisites (b -> a edges for each pair [a, b]). This will allow quick lookup of subsequent courses for any given course.
Use a Status Array for Each Course: Maintain an array or map status for each course to track its state in the DFS traversal. For example, use:
- 0 to mark not visited yet,
- 1 to mark visiting (currently in the DFS recursion stack),
- 2 to mark visited (DFS fully completed for this course).
  This is a typical “white-gray-black” marking technique for cycle detection in DFS.
DFS Traversal and Cycle Detection: Iterate through each course 0 to numCourses-1. If a course is not yet visited (status[i] == 0), start a DFS from that course. In the DFS function for course c:
- Mark c as visiting (status[c] = 1).
- For each neighbor n of c in the adjacency list (courses that depend on c), check:
  - If n is visiting (status[n] == 1), it means we found a back-edge to a course that is in the current path, i.e. a cycle exists . In this case, we can immediately conclude it’s impossible to finish all courses and return false.
  - If n is not visited (status[n] == 0), recursively DFS on n. If the DFS call on n finds a cycle (returns false), propagate the false result upward.
  - If n is already visited (status[n] == 2), it means that course (and all its descendants) has been fully processed before with no cycles found there, so we can safely skip it.
- After exploring all neighbors of c, mark c as visited (status[c] = 2) – meaning this course has no cycle in its prerequisite chain, and DFS for c is done.
Result: If the DFS traversal completes for all courses without detecting a cycle, return true (all courses can be finished). If any cycle was detected during the DFS, return false immediately. This approach directly checks for cycles in the graph via DFS.

Why This Works: In a directed graph, a cycle is exactly the situation where a node is revisited before the earlier visit is complete. By marking nodes as “visiting” and checking for a revisit, we can catch cycles. If no cycle is found, the DFS effectively produces a topological ordering (in the reverse of the finishing times). This is another way to confirm all courses can be completed, since a topological sort exists if and only if the graph has no cycle.

Python – DFS Approach (Cycle Detection):

Python3

. . . .

Explanation: We construct the adjacency list graph similarly. The status list keeps track of each node’s state (unvisited, visiting, or visited). We then iterate through each course; if it’s unvisited, we perform a DFS from that course. During DFS, if we encounter a course that is marked visiting (status 1), it means we’ve found a cycle and we return False immediately. We mark a course as visited (status 2) only after exploring all its descendants safely. If the DFS completes without finding any cycle for all starting nodes, we return True. This effectively checks all connected components of the graph for cycles.

Java – DFS Approach (Cycle Detection):

Java

. . . .

Explanation: We build the graph adjacency list with ArrayLists for each course. The status array tracks the visitation state of each course during DFS. We iterate over all courses and initiate a DFS for each unvisited course. The dfs method marks the current course as visiting, then explores its neighbors. If it finds a neighbor that is already in the visiting state, it returns false (cycle found). If a neighbor is unvisited, it calls DFS on that neighbor. After exploring all neighbors, it marks the current course as visited and returns true. If any DFS call returns false, we propagate that result up and return false from canFinish. If all DFS calls succeed, it means no cycles were found, and we return true.

Complexity Analysis:

Time Complexity: Both approaches run in linear time relative to the size of the graph. We process each course (vertex) and each prerequisite (edge) essentially once. This gives a time complexity of O(V + E), where V is numCourses and E is the number of prerequisite pairs. In the BFS approach, each course is enqueued and dequeued at most once, and we iterate over all edges in the adjacency list. In the DFS approach, each course is visited once and each edge is explored once during the depth-first traversal. Thus, both approaches are linear in the size of the input graph.
Space Complexity: Both solutions also use O(V + E) space . We need O(V + E) to store the graph in adjacency list form. The BFS approach uses additional O(V) space for the indegree array and up to O(V) for the queue in the worst case. The DFS approach uses O(V) space for the status array and the recursion stack (which in worst case can be O(V) deep). In Big-O terms, the overall space is linear in the number of courses plus prerequisites.

(In practice, the BFS approach might use slightly more space for the queue and indegree list, while DFS uses space for recursion. But both are linear scale, and neither should exceed the input size by more than a constant factor.)

Step-by-Step Walkthrough with Examples:

Let’s walk through a sample scenario to illustrate both approaches:

Suppose numCourses = 4 and prerequisites = [[1,0], [2,0], [3,1], [3,2]]. This means:

Course 1 depends on 0,
Course 2 depends on 0,
Course 3 depends on 1, and
Course 3 depends on 2.

In graph terms, we have edges: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. The graph (dependency graph) looks like this: 0 → 1, 0 → 2, 1 → 3, 2 → 3. There are no cycles in this graph, so we expect the result to be true (all courses can be finished). A valid order would be 0 → (1 and 2 in any order) → 3.

BFS (Kahn’s Algorithm) Walkthrough:

Initial Setup:
- Adjacency list: {0: [1, 2], 1: [3], 2: [3], 3: []}.
- Indegree array: [0, 1, 1, 2] (Course 0 has 0 prerequisites; 1 and 2 have 1 each (both depend on 0); 3 has 2 prerequisites (depends on 1 and 2)).
- Initial queue: [0] (only course 0 has no prerequisites).
Step 1: Dequeue course 0 (indegree 0). Mark course 0 as taken.
- Result (order so far): [0]
- Process neighbors of 0: courses 1 and 2 both depend on 0, so reduce their indegree by 1.
- Update indegree: Course 1 indegree becomes 0, Course 2 indegree becomes 0, Course 3 indegree remains 2.
- Enqueue any new indegree-0 courses: add course 1 and course 2 to queue.
- Queue now: [1, 2].
Step 2: Dequeue course 1. Mark course 1 as taken.
- Result: [0, 1]
- Neighbors of 1: course 3 depends on 1, so reduce indegree of 3 by 1.
- Update indegree: Course 3 indegree becomes 1.
- Enqueue new indegree-0 courses: (course 3 is not yet 0, so not added).
- Queue now: [2] (course 2 is next).
Step 3: Dequeue course 2. Mark course 2 as taken.
- Result: [0, 1, 2]
- Neighbors of 2: course 3 depends on 2, reduce indegree of 3 by 1.
- Update indegree: Course 3 indegree becomes 0 (it had 1 left, now 0).
- Enqueue new indegree-0 course: add course 3 to queue.
- Queue now: [3].
Step 4: Dequeue course 3. Mark course 3 as taken.
- Result: [0, 1, 2, 3]
- Neighbors of 3: (none, course 3 has no dependents).
- Queue becomes empty.
Completion: We took all 4 courses. The taken_count would be 4, which equals numCourses. This means all courses have been successfully ordered and taken with no issues. The algorithm returns true. (One possible valid order is 0 → 1 → 2 → 3, though 0 → 2 → 1 → 3 would also be valid in this case.)

Throughout this BFS process, if at any point we had courses remaining with nonzero indegree but the queue became empty, that would indicate a cycle. For example, in Example 2 earlier (0 -> 1 and 1 -> 0), initially indegree would be [1, 1] and queue would start empty (no course with indegree 0). The algorithm would finish without taking any course (taken_count = 0, which is not equal to numCourses 2), signaling that a cycle prevented any valid ordering – thus returning false.

DFS Walkthrough: (Using the same example graph as above)
We perform DFS on each course, using the status array to watch for cycles. Initially all courses are unvisited (status 0).

Start DFS at course 0:
- Mark 0 as visiting (status[0] = 1).
- Visit neighbors of 0. The neighbors are 1 and 2.
- DFS into course 1 (neighbor of 0):
  - Mark 1 as visiting (status[1] = 1).
  - Visit neighbor of 1, which is course 3.
  - DFS into course 3 (neighbor of 1):
    - Mark 3 as visiting (status[3] = 1).
    - Neighbors of 3: (none, since no course depends on 3).
    - No neighbors to explore, mark 3 as visited (status[3] = 2) and return True (no cycle found in this path).
  - Backtrack to course 1: all neighbors of 1 have been processed (course 3 was done). Mark 1 as visited (status[1] = 2) and return True to its caller.
- Backtrack to course 0: now explore the next neighbor of 0, which is course 2 (since 1 was done).
- DFS into course 2 (neighbor of 0):
  - Mark 2 as visiting (status[2] = 1).
  - Visit neighbor of 2, which is course 3.
  - Course 3’s status at this point is 2 (already visited in the previous DFS branch via course 1). A status of 2 means it’s fully processed, so we don’t need to DFS into 3 again; importantly, it’s not a cycle just to see a visited node. (We only worry if we see a neighbor with status 1, i.e., currently in recursion stack, which is not the case here — 3 is status 2.)
  - No other neighbors for 2, so mark 2 as visited (status[2] = 2) and return True.
- Backtrack to course 0: all neighbors (1 and 2) have been processed without finding a cycle. Mark 0 as visited (status[0] = 2) and return True.
DFS from course 0 succeeded with no cycles. Now, back in the outer loop, we check the next courses 1, 2, 3: but all of them are already marked as visited (status 2) from the previous traversal. So we do not start new DFS on 1, 2, or 3 since they’re already done.
Since we have processed all courses and never encountered a cycle, the algorithm returns true (all courses can be completed).

To see how the DFS catches cycles, consider the earlier Example 2 (cycle case with 0->1 and 1->0):

Start DFS at 0: mark 0 visiting. Neighbor is 1 → DFS into 1, mark 1 visiting. Neighbor of 1 is 0, but 0 is already in visiting state (we came from 0 and haven’t finished it yet). This means we found a back edge to 0, indicating a cycle. The DFS immediately returns false, which propagates out and causes the result to be false. This matches our expectation that the presence of a cycle should make the result false.

Common Mistakes & Edge Cases:

Incorrect Graph Edge Direction: A common mistake is flipping the edge direction. Remember that [a, b] means an edge from b to a (take b before a). Building the graph incorrectly will lead to wrong results. Always double-check that your adjacency list and indegree calculations reflect “prerequisite → course” direction.
Not Exploring All Components: Ensure that you consider all courses, including those that are isolated or not explicitly listed in prerequisites. In BFS, initialize the queue with all courses that have indegree 0 (there could be multiple). In DFS, run a DFS from every course that hasn’t been visited yet. This handles disconnected subgraphs of the course graph. If you only start from course 0 (for example), you might miss other components.
Cycle Detection in DFS: In the DFS approach, forgetting to mark a node as visiting (or not marking it back to unvisited correctly when backtracking in other problems) can fail to catch cycles or cause infinite recursion. Using the three-state method (unvisited/visiting/visited) is crucial. Also, not returning immediately when a cycle is found can lead to unnecessary processing — once you detect a cycle, you can stop.
Handling No Prerequisites: If prerequisites is empty, the function should trivially return true, since no course has any dependency. Both approaches naturally handle this (BFS queue will start with all courses, DFS will mark all as visited without any cycle). Just be mindful to handle this case (e.g., not dividing by zero or iterating an empty list incorrectly).
Large Input Performance: Both solutions are linear, which is efficient for the given constraints. However, be careful with recursive DFS in languages where stack depth is a concern (in Python, recursion depth limit might be an issue for very large graphs, though 2000 courses is fine). In Java, 2000 depth is safe, but always mark visited properly to avoid deeper unnecessary recursion. An infinite recursion usually means a cycle wasn’t caught due to a logic bug in marking states.

Alternative Variations and Related Problems:

Course Schedule II: Instead of just checking if you can finish, this variation asks you to return an order in which to take the courses (one valid topological ordering of the graph). The problem is solved with similar logic (BFS or DFS) but you collect the ordering. The BFS (Kahn’s algorithm) approach naturally produces a topological order by the sequence in which courses are taken. The DFS approach can produce an order by recording post-order of the DFS (and reversing it). This is a direct extension once you know how to detect feasibility.
Parallel Courses / Minimum Semesters: A variant where you can take multiple courses in one semester if they have no prerequisites in that semester. It asks for the minimum number of semesters to finish all courses. This can be solved by topological sort as well, using BFS layer by layer (counting levels in the DAG). It’s related to finding the longest path length in the DAG (since the longest prerequisite chain dictates the minimum semesters).
Alien Dictionary (LeetCode 269): Determines a valid alphabetical order of characters given words in sorted order. This is effectively a topological sort problem on a graph of characters. The concept of using indegree (BFS) or DFS to detect cycles is the same — if there’s a cycle, it means the dictionary order is invalid.
Prerequisite Tasks (various formulations): Many task scheduling problems with prerequisites are essentially the same topological sorting problem. For example, determining if a set of tasks can be completed given prerequisites, or outputting an order to complete them, uses the same graph techniques.
General Graph Cycle Detection: The DFS approach here is a specific case of detecting cycles in a directed graph. This technique (using a recursion stack or color marking) is widely applicable to any directed graph to check if it’s acyclic.