Typorithm · medium

Course Schedule

course-schedulegraphsadjacency-listcycle-detectionthree-color

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Course Schedule

Graphs

Model prerequisites as an adjacency list, then DFS with three colors; a back edge to a gray node means a cycle.

Courses can be finished only if their prerequisite graph has no cycle.

Build an adjacency list mapping each course to its prerequisites.

A three-color DFS — unvisited, visiting, done — detects a cycle when it reaches a node still in the 'visiting' state.

Adjacency list from edges.

Gray (1) on the stack, black (2) done.

Revisiting gray = cycle = cannot finish.

function canFinish(numCourses, prerequisites) {
  const graph = new Map();
  for (let i = 0; i < numCourses; i += 1) {
    graph.set(i, []);
  }
  for (const [course, prereq] of prerequisites) {
    graph.get(course).push(prereq);
  }

  const state = new Array(numCourses).fill(0);

  function hasCycle(course) {
    if (state[course] === 1) {
      return true;
    }
    if (state[course] === 2) {
      return false;
    }
    state[course] = 1;
    for (const prereq of graph.get(course)) {
      if (hasCycle(prereq)) {
        return true;
      }
    }
    state[course] = 2;
    return false;
  }

  for (let i = 0; i < numCourses; i += 1) {
    if (hasCycle(i)) {
      return false;
    }
  }
  return true;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Build adjacency

Each course points to its prerequisites.

graph.get(course).push(prereq)

2. Back edge = cycle

Re-entering a node still on the stack means a cycle.

if (state[course] === 1) {
      return true;
    }

3. Already cleared

A fully explored node is known to be cycle-free.

if (state[course] === 2) {
      return false;
    }

4. Mark visiting

Color the node gray while exploring its descendants.

state[course] = 1

5. Mark done

Color it black once all prerequisites clear.

state[course] = 2

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.