207. Course Schedule

Course Schedule (LeetCode 207) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Cycle Detection (Directed Graph) subpattern.

• Blind 75 · #45 of 75 · Graphs
• NeetCode 150 · #87 of 150 · Graphs
• NeetCode 250 · #154 of 250 · Graphs

How to solve Course Schedule

Course Schedule is a Cycle Detection in Directed Graph problem, part of Graph Traversal Patterns (DFS & BFS). Detect cycles in directed graphs using DFS with coloring (white, gray, black) approach.

Work towards the solution in these steps:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. <a href="https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/03Graphs.pdf" target="_blank">Topological Sort via DFS</a> - A great tutorial explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via <a href="http://en.wikipedia.org/wiki/Topological_sorting#Algorithms" target="_blank">BFS</a>.

The reference solution runs in O(V + E) time and O(V + E) space.

The Course Schedule solution and editorial walks through the full approach with reference code.

Problem statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

- For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

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.

Constraints:

- 1 <= numCourses <= 2000

- 0 <= prerequisites.length <= 5000

- prerequisites[i].length == 2

- 0 <= ai, bi < numCourses

- All the pairs prerequisites[i] are unique.

Topics and companies

Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort.

Reported in interviews at Amazon, Bloomberg, ByteDance, Facebook, Google, Intuit, Karat, Microsoft, Uber.

How to practise Course Schedule on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(V + E) time and O(V + E) space.

Open Course Schedule in the code editor, or read the Course Schedule editorial for a worked solution with its approach and complexity analysis.

Where Course Schedule sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Cycle Detection (Directed Graph) subpattern
• The full DSA patterns sheet

Problems related to Course Schedule

Other problems that use the same Graph DFS - Cycle Detection (Directed Graph) and Graph Traversal Patterns (DFS & BFS) techniques:

• All Paths from Source Lead to Destination — Medium, same subpattern
• Course Schedule II — Medium, same subpattern
• Find Eventual Safe States — Medium, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• Build a Matrix With Conditions — Hard, same pattern

Course Schedule FAQ