Skip to main content
SeniorPath
Browse content
Menu / Close menu

March 24

Course Schedule

How to turn prerequisites into a directed graph and detect when a dependency comes back to itself.

Graphs Intermediate 25 min TypeScript

#interviews#graphs#topological-sort#bfs#dfs

You have numCourses courses labeled from 0 to numCourses - 1.

Each pair in prerequisites has the form [course, prereq] and means:

  • to take course, you must finish prereq first

Return true if it is possible to finish all courses. Otherwise, return false.

Example:

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

What to notice before coding

  • The problem does not necessarily ask you to produce the final order. It asks whether a cycle exists.
  • Dependency creates a directed graph, not just any graph.
  • Visiting a node that is already in the current path means a cycle.

Common mistakes

  • using one `visited` flag and missing the difference between "visiting now" and "already finished"
  • repeating the same search too many times without remembering resolved nodes

Step 1 - Translate the statement into a graph

The statement becomes much clearer when you stop thinking in "pairs" and start thinking in graphs:

  • each course is a vertex
  • each dependency is a directed edge

If one course depends on another, there is an arrow in that relationship.

Step 2 - Understand what makes the answer impossible

The only real way to fail is a cycle.

Example:

  • course 0 depends on 1
  • course 1 depends on 0

That means neither of them can start.

Step 3 - Write the most direct baseline

A reasonable baseline is:

  • build the graph
  • for each course, run DFS with a Hash Set for the current path
  • if some course returns to a node already in that path, there is a cycle

It works.

But it can repeat the same exploration many times.

Step 4 - Separate "visiting" from "already resolved"

This is where three useful states help:

  • 0: never seen
  • 1: visiting now
  • 2: already explored below and known to be safe

If you enter a node with state 1, you found a cycle. If you enter a node with state 2, there is no need to explore it again.

The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.

Starter code

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // your solution here
  return false
}
solution.ts
Stuck? Hints available.

Haven't solved it yet?

Viewing the solution now may reduce learning. It's worth trying a bit more.

Open the reference solution

Without JavaScript, the reference solution is shown inline instead of in a dialog.

Solution

Final complexity

Time: O(V + E)

Space: O(V + E)

Solution 1 - DFS with a current-path Hash Set

Good baseline because the cycle idea stays very visible.

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph = Array.from({ length: numCourses }, () => [])

  for (const [course, prereq] of prerequisites) {
    graph[course].push(prereq)
  }

  function hasCycle(course: number, path: Set<number>): boolean {
    if (path.has(course)) {
      return true
    }

    path.add(course)

    for (const prereq of graph[course]) {
      if (hasCycle(prereq, path)) {
        return true
      }
    }

    path.delete(course)
    return false
  }

  for (let course = 0; course < numCourses; course += 1) {
    if (hasCycle(course, new Set())) {
      return false
    }
  }

  return true
}

It works, but it repeats too much work.

Solution 2 - DFS with three states

Now each course is explored more intelligently.

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph = Array.from({ length: numCourses }, () => [])

  for (const [course, prereq] of prerequisites) {
    graph[course].push(prereq)
  }

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

  function dfs(course: number): boolean {
    if (state[course] === 1) {
      return false
    }

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

    state[course] = 1

    for (const prereq of graph[course]) {
      if (!dfs(prereq)) {
        return false
      }
    }

    state[course] = 2
    return true
  }

  for (let course = 0; course < numCourses; course += 1) {
    if (!dfs(course)) {
      return false
    }
  }

  return true
}

The strong insight is not recursion by itself. It is separating “currently on the path” from “already known to be safe.”

What to say in the interview

A strong short explanation would be:

I model the courses as a directed dependency graph. The problem becomes cycle detection. In the stronger version I use DFS with three states: unvisited, visiting, and resolved. If I hit a node in the visiting state again, I found a cycle. If the node is already resolved, I skip reprocessing it. A topological sort view leads to the same answer from the BFS side.

That shows that you:

  • translated the problem into the right model
  • identified the real cause of failure
  • explained the memoization win in the DFS

When this pattern shows up again

This pattern comes back when you need to:

  • validate dependencies in directed graphs
  • detect cycles in build systems, package managers, and scheduling
  • use DFS with per-node state
  • compare DFS against BFS using topological sort

The point is not memorizing Course Schedule.

The point is learning to recognize dependencies as a directed graph.
Next challenge Generate Parentheses Previous challenge LRU Cache

Related challenges

Number of Islands

Longest Substring Without Repeating Characters

3Sum

Related articles

Thinking Before You Code in Interviews

Recognizing Problem Patterns

How to Explain Your Solution Without Getting Lost