Course Schedule
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 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 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.
Example 3:
Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
Output: true
Explanation: There are 4 courses forming a linear chain: 0 → 1 → 2 → 3.
Take them in order 0, 1, 2, 3.
Examples
Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are 2 courses. To take course 1, you must first finish course 0. This is achievable by taking course 0 first, then course 1.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Course 1 requires course 0, and course 0 requires course 1. This creates a circular dependency (cycle), making it impossible to finish all courses.
Example 3
Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
Output: true
Explanation: The courses form a linear dependency chain 0 → 1 → 2 → 3 with no cycles. Take them in order: 0, 1, 2, 3.
Constraints
- -1 <= numCourses <= 2000
- -0 <= prerequisites.length <= 5000
- -prerequisites[i].length == 2
- -0 <= ai, bi < numCourses
- -All the pairs prerequisites[i] are unique.
Optimal Complexity
Time
O(V + E)
Space
O(V + E)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview