Solution

You'll decide whether a set of courses can all be finished by checking one thing about their prerequisite graph: does it contain a cycle? If it does, the plan is impossible; if it doesn't, every course can be ordered so its prerequisites come first.

The problem, in plain English

You have courses numbered 0 to numCourses - 1 and a list of pairs like [1, 0], meaning "course 0 must be taken before course 1." Think of each pair as a directed arrow: 0 -> 1. A student can finish everything only if they can lay all the courses out in a line where every arrow points forward — you never have to take a course before something it depends on.

That ordering exists exactly when the graph has no cycle. If 0 -> 1 and 1 -> 0, there's no valid first course: 0 is waiting on 1, and 1 is waiting on 0. The same trap hides in longer loops (0 -> 1 -> 2 -> 0) and in a single self-loop (0 -> 0, "course 0 requires course 0"). So the whole question reduces to: is this directed graph acyclic?

The mental model

There are two classic ways to detect a cycle in a directed graph, and we'll build toward one of them.

The first idea — Kahn's algorithm — leans on a single observation: a course with no remaining prerequisites can always be taken right now. So count, for each course, how many prerequisites point at it. That count is its indegree (the number of incoming arrows). Repeatedly take any course whose indegree is 0, "complete" it, and decrement the indegree of every course that depended on it. If you manage to complete all numCourses courses this way, there was no cycle. If you get stuck — some courses still have a positive indegree but none are at 0 — those courses are tangled in a cycle, each waiting on another.

The key state is one array and one queue:

• indegree[c] — how many prerequisites course c is still waiting on.
• a queue of "ready" courses — every course currently at indegree 0.
• processed — a running count of how many courses we've completed. The final verdict is processed === numCourses.

A first attempt

Before reaching for indegrees, most people try a plain depth-first search: walk the graph, mark each node "visited," and if you ever reach a node again, call it a cycle.

function naiveDfs(numCourses, prerequisites) {
  const adj = buildAdjacency(numCourses, prerequisites);
  const visited = new Set();

  function dfs(course) {
    if (visited.has(course)) return true; // "seen it -> must be a cycle"
    visited.add(course);
    for (const next of adj[course]) {
      if (dfs(next)) return true;
    }
    return false;
  }

  for (let c = 0; c < numCourses; c++) {
    if (dfs(c)) return false; // found a cycle -> impossible
  }
  return true;
}

This looks reasonable and even passes the simplest tests. But it's wrong, and the bug is subtle: a visited set can't tell a cycle from a node you simply reached twice by different routes.

Take the re-converging graph 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. This is a diamond — node 3 is reachable from both 1 and 2, but there is no cycle. Walk it: dfs(0) visits 0, recurses into 1, then 3. Node 3 is marked visited. Back up, recurse into 2, then try 3 again — visited.has(3) is true, so the naive code shouts "cycle!" But re-reaching 3 here is perfectly fine; 3 is just a shared dependency, not part of a loop. The naive DFS produces a false positive on a graph that is actually finishable.

The missing distinction: "currently on the path I'm exploring" versus "finished exploring earlier." Re-entering a node still on the current call stack is a cycle. Re-entering a node you already finished is not.

The working solution

We'll use Kahn's algorithm — it sidesteps the gray/black bookkeeping entirely and gives us the cycle answer as a clean count. (The DFS fix is described right after, in Walking through one call and Gotchas, since it's the other canonical approach.)

function courseDependency(numCourses, prerequisites) {
  // adj[p] = list of courses that have p as a prerequisite (edges p -> course)
  const adj = Array.from({ length: numCourses }, () => []);
  // indegree[c] = how many prerequisites course c is still waiting on
  const indegree = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course); // prereq must come before course: edge prereq -> course
    indegree[course]++;       // course gains one incoming dependency
  }

  // Seed the queue with every course that has no prerequisites.
  const queue = [];
  for (let c = 0; c < numCourses; c++) {
    if (indegree[c] === 0) queue.push(c);
  }

  let processed = 0;
  while (queue.length > 0) {
    const course = queue.shift(); // any ready course; order doesn't affect the verdict
    processed++;
    for (const next of adj[course]) {
      indegree[next]--;                 // one of next's prerequisites is now done
      if (indegree[next] === 0) {        // all of next's prereqs satisfied -> it's ready
        queue.push(next);
      }
    }
  }

  // If we couldn't process every course, the leftovers are stuck in a cycle.
  return processed === numCourses;
}

module.exports = { courseDependency };

A few choices deserve their why:

Why we build adjacency as prereq -> course, not course -> prereq. The input pair [course, prereq] reads "prereq before course," which is the edge direction prereq -> course. We want to ask "once prereq is done, which courses become more ready?" — so the adjacency list must point from a prerequisite to the courses that depend on it. Reversing this is the single most common bug: it computes the cycle answer on the transposed graph, which happens to give the right boolean (a graph has a cycle iff its reverse does), but any code you later add to produce the actual order would be backwards.

Why a self-loop [0, 0] is caught for free. The pair [0, 0] runs adj[0].push(0) and indegree[0]++, so course 0 starts at indegree 1. Nothing ever decrements it (the only edge into 0 comes from 0 itself, which never gets processed), so 0 is never queued, processed stays below numCourses, and we return false. No special-casing needed.

Why processed === numCourses is the cycle test. Every course that ever reaches indegree 0 gets queued exactly once and processed exactly once. A course trapped in a cycle never hits indegree 0 — it always has at least one unsatisfied prerequisite from another node in the loop — so it's never processed. If the count falls short, some courses were unreachable from any zero-indegree start, which can only happen if they're locked in a cycle.

Why duplicate edges don't cause a false cycle. Two copies of [1, 0] bump indegree[1] to 2 and push 1 into adj[0] twice. Processing 0 then decrements indegree[1] twice, back to 0, and 1 is queued once (it only hits 0 on the second decrement). The bookkeeping stays consistent — the count of incoming edges and the count of decrements match.

Walking through one call

Success case — the diamond 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3 (input [[1,0],[2,0],[3,1],[3,2]], numCourses = 4).

build:   indegree = [0, 1, 1, 2]   (0 has none; 1,2 wait on 0; 3 waits on 1 and 2)
         adj = { 0: [1, 2], 1: [3], 2: [3], 3: [] }

seed:    queue = [0]                (only course 0 has indegree 0)
         processed = 0

pop 0    processed = 1
         decrement 1 -> 0  -> queue [1]
         decrement 2 -> 0  -> queue [1, 2]

pop 1    processed = 2
         decrement 3 -> 1  (not zero yet; 3 still waits on 2)
         queue = [2]

pop 2    processed = 3
         decrement 3 -> 0  -> queue [3]

pop 3    processed = 4
         3 has no dependents; nothing to decrement
         queue = []

result:  processed (4) === numCourses (4) -> true

Node 3 is reached twice — once via 1, once via 2 — and that is exactly the case the naive DFS mishandled. Here it's a non-event: the second decrement just brings 3's indegree to 0 and queues it. No false cycle.

Failure case — 0 -> 1 plus the cycle 1 -> 2, 2 -> 1 (input [[1,0],[2,1],[1,2]], numCourses = 3).

build:   indegree = [0, 2, 1]      (1 waits on 0 AND 2; 2 waits on 1)
         adj = { 0: [1], 1: [2], 2: [1] }

seed:    queue = [0]               (only 0 is at indegree 0)

pop 0    processed = 1
         decrement 1 -> 1          (still waiting on 2; not queued)
         queue = []

result:  processed (1) < numCourses (3) -> false

After course 0 is done, courses 1 and 2 each still wait on the other. Neither ever reaches indegree 0, the queue drains, and processed is stuck at 1. Short of 3, so we return false.

The DFS alternative, fixed. If you prefer DFS, the repair for the naive version is the gray/black distinction: mark a node gray when you enter it (it's on the current path) and black when you finish all its descendants. Hitting a gray node mid-traversal is a back edge — a real cycle. Hitting a black node is a node you already fully explored on another branch — safe, not a cycle. That single change fixes the diamond false-positive: when DFS re-reaches node 3 in the diamond, 3 is already black, so it's skipped instead of flagged.

Gotchas

• visited-only DFS reports false cycles on re-converging graphs. A plain visited set can't tell "still on my current path" from "finished long ago." On the diamond 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, re-reaching 3 via the second branch looks like a repeat and gets flagged as a cycle — but it's a finishable graph. Fix: use three states (white/gray/black), and only treat re-entering a gray (on-path) node as a cycle.
• Reversing the edge direction. [course, prereq] means prereq -> course. If you build adj[course].push(prereq) instead, you've transposed the graph. The boolean answer happens to survive (a graph has a cycle iff its reverse does), but it's a latent bug — the moment you extend this to return the actual ordering, you'll emit it backwards.
• Forgetting the self-loop. [0, 0] is a one-course cycle: course 0 requires itself. In Kahn's it's automatic (indegree 0 starts at 1 and never drains). In DFS you must let a node's edge to itself count as reaching a gray node — don't special-case "skip the node I'm currently on," or you'll miss it.
• Counting the wrong thing for the verdict. The cycle test is processed === numCourses, not "did the queue ever go empty" (it always does) and not "are all indegrees zero" (you'd have to re-scan). Track the processed count as you pop; compare once at the end.
• A re-converging DAG is not a cycle. Shared dependencies (a node reached by multiple paths) are normal and finishable. Don't conflate "multiple incoming edges" with "cycle." Indegree counts the incoming edges precisely because a node can legitimately have several.
• Mutating the input. Build a fresh indegree array and adjacency list; don't decrement counts on a structure the caller still holds. The solution above allocates its own, so repeated calls with the same prerequisites are independent.

Going further

• Return a valid order (topological sort). Kahn's already computes it: instead of just counting processed, push each popped course onto an order array. If order.length === numCourses, return order — that's a valid sequence to take the courses in. This is the "Course Schedule II" problem; the cycle case returns an empty array.
• Find and report the actual cycle. A boolean tells you a plan is impossible but not why. With the gray/black DFS, keep a parent pointer (or an explicit path stack); when you hit a gray node, walk the stack from the current node back to that gray node to extract the exact courses in the loop — useful error messaging for a real planner (0 -> 1 -> 2 -> 0).
• Handle huge graphs without recursion. Deep prerequisite chains can blow the call stack in recursive DFS. Kahn's is already iterative. If you want iterative DFS, simulate the call stack explicitly with an array and push the gray/black transitions as you go. Both run in O(numCourses + prerequisites.length) time and linear space.