#207 Course Schedule
frequently reported atByteDance / TikTokAmazonAppleMetaUberMicrosoft
the problem
In plain words
There are numCourses courses labelled 0..numCourses−1. prerequisites[i] = [a, b] means you must take b before a. Return true if you can finish all courses.
in numCourses = 2, prerequisites = [[1,0]]
out true
Take 0, then 1.
in numCourses = 2, prerequisites = [[1,0],[0,1]]
out false
0 needs 1 and 1 needs 0 — a cycle.
- 1 ≤ numCourses ≤ 2000
- 0 ≤ prerequisites.length ≤ 5000
- All pairs are unique
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTopological sort & cycle detection
"Can I finish everything?" is exactly "does the prerequisite graph have no directed cycle?"
solutions
From brute force to optimal
Find any course whose prerequisites are all taken, take it, repeat. If you get stuck early, there's a cycle.
- Repeat numCourses times: scan all courses for one whose every prerequisite is taken.
- None found → return false.
- Otherwise mark it taken.
Up to V rounds × V candidate courses × E prerequisite checks each.
Just the taken[] flags.
class Solution { /** Repeatedly delete a course with no remaining prerequisites. Stuck before the end → cycle. */ public boolean canFinish(int numCourses, int[][] prerequisites) { boolean[] taken = new boolean[numCourses]; for (int round = 0; round < numCourses; round++) { int pick = -1; for (int c = 0; c < numCourses && pick == -1; c++) { if (taken[c]) continue; boolean ready = true; for (int[] p : prerequisites) { if (p[0] == c && !taken[p[1]]) { ready = false; break; } } if (ready) pick = c; } if (pick == -1) return false; // every remaining course waits on another one taken[pick] = true; } return true; }}Same idea made fast: keep in-degrees so "free" courses are found in O(1) via a queue.
- Build pre → course adjacency and in-degrees.
- Queue all in-degree-0 courses.
- Poll, count, decrement neighbours, enqueue new zeros.
- Return count == numCourses.
Each course polled once, each edge decremented once.
Adjacency list, in-degree array, queue.
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>()); int[] indegree = new int[numCourses]; for (int[] p : prerequisites) { // p = {course, pre}: edge pre → course adj.get(p[1]).add(p[0]); indegree[p[0]]++; } Deque<Integer> queue = new ArrayDeque<>(); for (int c = 0; c < numCourses; c++) { if (indegree[c] == 0) queue.offer(c); } int taken = 0; while (!queue.isEmpty()) { int u = queue.poll(); taken++; for (int v : adj.get(u)) { indegree[v]--; if (indegree[v] == 0) queue.offer(v); } } return taken == numCourses; // courses on a cycle never reach in-degree 0 }}Kahn dry run (input is [course, pre])
A cycle exists iff DFS meets a gray vertex (one still on the current path).
- Colour all white.
- DFS: paint gray on entry; edge to gray → cycle; recurse into white; paint black on exit.
- Start a DFS from every white vertex.
Each vertex turns gray and black once; each edge is checked once.
Adjacency list plus colours and up to V recursion frames.
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>()); for (int[] p : prerequisites) adj.get(p[1]).add(p[0]); // pre → course int[] color = new int[numCourses]; // 0 white, 1 gray (on the path), 2 black (safe) for (int c = 0; c < numCourses; c++) { if (color[c] == 0 && hasCycle(c, adj, color)) return false; } return true; } private boolean hasCycle(int u, List<List<Integer>> adj, int[] color) { color[u] = 1; for (int v : adj.get(u)) { if (color[v] == 1) return true; if (color[v] == 0 && hasCycle(v, adj, color)) return true; } color[u] = 2; return false; }}Find the back edge
in the room
How to say it in the interview
talk track
- Restate: "Courses are vertices, [a, b] is an edge b → a. I need to know if this directed graph has a cycle."
- Offer Kahn: in-degrees, queue the zeros, count how many we can take. If count < n, the rest are stuck on a cycle.
- Mention DFS colours as the alternative and why two states aren't enough.
- Complexity: O(V + E) time and space.
traps
- Building the edge as a → b instead of b → a still answers 207 correctly (a cycle is a cycle in either direction) — but it breaks 210, so build it right from the start.
what they ask next
Follow-ups
Return an actual order (LC 210)?
Record the polled vertices in Kahn (or reverse the DFS finish order).
Many queries "is course a a prerequisite of b?" (LC 1462)?
numCourses ≤ 100, so precompute full reachability: walk courses in topological order and copy each course's prerequisite set into its dependants — O(V · (V + E)) — then answer each query in O(1).
before you submit
Edge cases to test
- No prerequisites at all → true.
- A self-loop [0, 0] → false.
- A diamond (two courses share a prerequisite and both lead to one course) is not a cycle → true.
- The cycle can sit in a part of the graph that course 0 never reaches.
practise next
Similar problems
- #210Course Schedule IIMediumin Topo Sort
- #802Find Eventual Safe StatesMediumin Topo Sort
- #261Graph Valid TreeMediumin Union-Find & MSTLeetCode Premium