All problems
MediumGraphs

Course Schedule

amazonmetamicrosoftgoogleapplebloomberg

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.

Examples

Example 1
Input
numCourses = 2, prerequisites = [[1,0]]
Output
true

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

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

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)

One problem, two ways to prep

Choose between solo practice and interview simulation

Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.

Try 5-Minute Audio InterviewAI Interview Mode