Course Schedule

You must take numCourses courses labelled 0 .. numCourses-1. Some have prerequisites: prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, and false otherwise.

Hints

· Stuck? Reveal one nudge at a time.

Model prerequisites as a directed graph: [a, b] means an edge b -> a.

You can finish all courses iff this graph has no directed cycle.

Use Kahn's algorithm (order all courses) or DFS (detect a back edge).

Common doubts

[a, b] means 'b before a', so the dependency edge is b -> a.

A DAG has a topological order — a valid sequence to take the courses; a cycle makes some courses mutually blocked.

Either — both O(V+E). Kahn also yields a valid order; DFS also pinpoints the blocking cycle.

Interview follow-ups

· What an interviewer asks next.

That's Course Schedule II — output the topological order (or empty if a cycle exists).

A self-loop is an immediate cycle, so it's unfinishable.

Fun facts

LeetCode 207 — the canonical 'is it a DAG?' interview question.
The same model handles build systems, package managers, and spreadsheet recalculation.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Take 0, then 1.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
0 and 1 each require the other — a cycle.

Constraints

- 1 <= numCourses <= 10^5 - 0 <= prerequisites.length <= 10^5 - no duplicate prerequisite pairs

Model prerequisites as a directed graph: [a, b] (take b before a) is an edge b → a. You can finish all courses iff this graph has no directed cycle — a cycle is a set of courses each waiting on another, impossible to start. So the whole problem is a directed-cycle test:

Kahn's algorithm — repeatedly remove courses with no remaining prerequisites (in-degree 0). If you manage to remove all numCourses, it's a DAG (finishable); if some remain, they're stuck in a cycle.
DFS with a recursion stack — a back edge to a course currently on the DFS path is a cycle.

Both are O(V + E).

Prerequisites

Before you start

· Concepts used directly in the solution.

Prereq graph. edge b -> a for 'b before a'.

Finishable ⟺ acyclic. a cycle makes some courses unstartable.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Direction of the edge?”

[a, b] means b before a, so the edge points b -> a.

“When is it impossible?”

Exactly when the prerequisite graph has a cycle.

The ideal opening — say it like this

Prerequisites form a directed graph; I can finish everything iff it has no cycle.

I run Kahn's and check all courses get ordered, or DFS for a back edge.

Understand the problem

Worked example — numCourses = 2, prerequisites = [[1,0],[0,1]]

edges 0->1 and 1->0 form a cycle -> no course has in-degree 0 -> cannot finish -> false

Key observations

1Aha

Prerequisites = directed edges

[a, b] ⇒ b → a.

2Aha

Finishable ⟺ no cycle

A DAG always has a valid order.

3Aha

Kahn orders all iff DAG

Leftover courses indicate a cycle.

Brute force vs optimal

	Kahn's algorithm	DFS recursion stack
Signal	ordered count == numCourses	no back edge
Time	O(V+E)	O(V+E)
Also gives	a valid order	the offending cycle

Both answer the same finishability question. Full code is in the Approaches selector below.

Summary

Key takeaway

You can finish all courses iff the prerequisite graph (edge b → a) is acyclic. Kahn's (order all V) or DFS (no back edge). O(V+E).

build edges b -> a
return "no directed cycle"