210. Course Schedule II
Course Schedule II (LeetCode 210) 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.
How to solve Course Schedule II
Course Schedule II 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:
- This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- <a href="https://www.youtube.com/watch?v=ozso3xxkVGU" target="_blank">Topological Sort via DFS</a> - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- 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(|E|) space.
The Course Schedule II 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 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
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph DFS - Cycle Detection (Directed Graph) subpattern
- The full DSA patterns 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:
- All Paths from Source Lead to Destination — Medium, same subpattern
- Course Schedule — 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 II FAQ
What is the LeetCode number of Course Schedule II?
Course Schedule II is LeetCode problem 210, rated Medium.
What pattern is used to solve Course Schedule II?
Course Schedule II is a Cycle Detection in Directed Graph problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Cycle Detection (Directed Graph) subpattern.
What is the time complexity of Course Schedule II?
The reference solution runs in O(|V| + |E|) time and O(|E|) space.
Which companies ask Course Schedule II?
Course Schedule II has been reported in interviews at Amazon, Bloomberg, DoorDash, Facebook, Google, Intuit, Karat, Microsoft, Oracle, Pinterest, Robinhood, Snapchat and others.