Course Schedule II

Course Schedule II 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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

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

Constraints:

- 1 <= numCourses <= 2000

- 0 <= prerequisites.length <= numCourses (numCourses - 1)

- prerequisites[i].length == 2

- 0 <= ai, bi < numCourses

- ai != bi

- All the pairs [ai, bi] are distinct.

Topics and companies

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

Reported in interviews at Amazon, Bloomberg, DoorDash, Facebook, Google, Intuit, Karat, Microsoft, Oracle, Pinterest, Robinhood, Snapchat and others.

How to practise Course Schedule II 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(|E|) space.

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

Where Course Schedule II sits in the DSA pattern sheet

Problems related to Course Schedule II

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

Preparing this workspace.