Skip to main content

207. Course Schedule

medium

Given prerequisites between courses, decide whether you can finish all of them. The textbook cycle-detection-in-a-directed-graph problem — either Kahn's BFS topological sort or DFS with three colors works.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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. Return true if you can finish all courses. Otherwise, return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Examples

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: 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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Model courses as nodes and prerequisites as directed edges. What property of that graph makes the schedule possible?

Hint 2

If the graph has no directed cycle, a valid order exists (topological sort). If it has a cycle, no order works.

Hint 3

Kahn's algorithm: compute in-degrees, push every 0-in-degree node into a queue, pop and decrement neighbors. If you pop numCourses nodes total, no cycle. Otherwise return false.

Solution approach

Reveal approach

Build an adjacency list from prerequisites — edge b -> a means b must come before a — and an in-degree array. Initialize a queue with every node whose in-degree is 0. Process the queue: pop a node, increment a popped counter, and decrement the in-degree of every neighbor; when a neighbor's in-degree hits 0, enqueue it. After the queue empties, return popped == numCourses. If a cycle exists, those cycle nodes' in-degrees never reach 0 so they're never enqueued. The DFS alternative uses three colors: white (unvisited), gray (in current path), black (fully done) — gray-on-gray means cycle. O(V + E) time, O(V + E) space for the adj list.

Complexity

Time
O(V + E)
Space
O(V + E)

Related patterns

  • topological-sort
  • dfs
  • bfs
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Apple

More Graphs practice problems

See all Graphs problems →