Course Schedule

Course Schedule 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.

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), where V is numCourses and E is the number of prerequisite pairs. We process each node and each edge once. time and O(V + E), for the adjacency list (O(E)), in-degree array (O(V)), and queue (O(V)). 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

Problems related to Course Schedule

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

Preparing this workspace.