139. Course Schedule

PRO

Medium

Topics

Companies

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

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

Output: true

Explanation: Course 1 depends on course 0. It is possible to finish course 0 and then course 1.

Example 2:

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

Output: false

Explanation: Course 0 depends on course 1, and course 1 depends on course 0. There is a cycle, so it is not possible to finish all courses.

Example 3:

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

Output: true

Explanation: Course 0 depends on course 1 and course 2. Course 1 depends on course 2. A possible order is 2 -> 1 -> 0.

Constraints:

•
•
•
•
•

Cycle detection in directed graph using DFS. Use 3 states: unvisited(0), visiting(1), visited(2). If we encounter a node in 'visiting' state during DFS, there's a cycle. Build adjacency list from prerequisites and check all nodes.

Time Complexity

O(V + E)

Space Complexity