‹ DS&A interview · Socratic
DSA · Graph / topological sort · #09

Course Schedule

Module 12 · difficulty 3/5·⏱ 30:00starts on first keystroke

There are `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [a, b]` means you must take course `b` first if you want to take course `a`. Return `true` if you can finish all courses. Otherwise, return `false`. Equivalent formulation: does the directed prerequisite graph contain a cycle?

Examples
  • numCourses = 2, prerequisites = [[1,0]] → true — take 0 then 1
  • numCourses = 2, prerequisites = [[1,0],[0,1]] → false — cycle 0 → 1 → 0
  • numCourses = 3, prerequisites = [] → true
Constraints
  • · 1 <= numCourses <= 2000
  • · 0 <= prerequisites.length <= 5000
  • · prerequisites[i].length == 2
  • · 0 <= a, b < numCourses
  • · All pairs prerequisites[i] are unique.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.