Graph Traversal: Solving the 'Course Schedule' Problem

The LeetCode 'Course Schedule' problem is asking one focused question: do the prerequisite relationships contain a cycle? Represent the courses as a directed graph and the scheduling story becomes a graph‑traversal problem. The useful step is recognising the cycle, not memorising a platform‑specific trick.

What's the 'Course Schedule' Problem Actually About?

The 'Course Schedule' problem (LeetCode #207) essentially asks us to figure out whether we can complete all courses, given a list of prerequisites. Each course might depend on another course being finished first.

Simple Example

Imagine we have four courses numbered from 0 to 3, with these prerequisites:

numCourses = 4;
prerequisites = [[1, 0], [2, 1], [3, 2]];

This means that:

• You need to finish course 0 before starting course 1.
• Course 1 must be completed before course 2.
• Course 2 must be completed before course 3.

In this situation, there's clearly a logical path through the courses, like this:

0 → 1 → 2 → 3

Because this is a straightforward chain without loops, it is possible to complete all four courses in order.

Example of a More Problematic Case

Now, imagine a slightly different scenario:

numCourses = 2;
prerequisites = [[1, 0], [0, 1]];

Here, we have:

• Course 0 requires course 1 to be completed first.
• Course 1 requires course 0 to be completed first.

In this scenario, the dependencies form a cycle:

0 → 1 → 0

Because each course indirectly depends upon itself, neither course can be completed. In this problem, our job is to detect these scenarios quickly.

Why is This a Graph Problem?

Each course can be viewed as a node in a graph, and the dependencies become directed edges pointing from one node (course) to another. Detecting if it is possible to complete all courses now becomes about finding cycles in a directed graph.

If a cycle exists, we simply cannot finish all the courses, it's as straightforward as that.

Solving the Problem Using Depth‑First Search (DFS)

One efficient way to detect cycles is using Depth‑First Search (DFS). Here's how we might approach this practically using JavaScript:

Step‑by‑Step Solution

1. Create an adjacency list to represent the graph of courses.
2. Traverse each node using DFS.
3. Keep track of visited nodes and nodes currently in the recursion stack.
4. We know we have found a cycle if we revisit a node already in the recursion stack.

A JavaScript/TypeScript implementation might look something like this:

const canFinish = (numCourses: number, prerequisites: number[][]): boolean => {
  const graph = Array.from({ length: numCourses }, () => [] as number[]);
  const visited = new Set<number>();
  const recStack = new Set<number>();

  prerequisites.forEach(([course, pre]) => {
    graph[pre].push(course);
  });

  const hasCycle = (course: number): boolean => {
    if (recStack.has(course)) return true;
    if (visited.has(course)) return false;

    visited.add(course);
    recStack.add(course);

    for (const neighbour of graph[course]) {
      if (hasCycle(neighbour)) return true;
    }

    recStack.delete(course);
    return false;
  };

  for (let i = 0; i < numCourses; i++) {
    if (!visited.has(i) && hasCycle(i)) {
      return false;  // cycle detected
    }
    visited.add(i);
  }

  return true;  // no cycles found
};

Why Does This Work?

• We know that if we encounter a node that is already in our recursion stack, then we have found a cycle.
• If we manage to traverse all of the nodes without encountering this, then the courses are safe to complete.

Adding Tests for Reliability

When it comes to tests like this, if you have been assigned it as part of an interview or technical assessment, then adding test coverage might just offer you an extra bit of credit. Testing is always important to ensure that our functions work in all scenarios and edge cases. It is trivially straightforward to add Jest coverage for our canFinish function:

test('detects no cycle correctly', () => {
  expect(canFinish(2, [[1, 0]])).toBe(true);
});

test('detects cycle correctly', () => {
  expect(canFinish(2, [[1, 0], [0, 1]])).toBe(false);
});

With these tests, you can quickly confirm that our function behaves as intended, catching potential issues early. This is especially handy if whomever has set this task for you has provided a list of example inputs and expected outputs.

Common Mistakes to Avoid

Not Marking Visited Nodes Properly

Forgetting to mark nodes as visited can lead to incorrect cycle detection. Ensure you carefully track each node you've processed.

Confusing Recursion and Visited States

Clearly distinguish between nodes currently in the recursion stack and nodes that have been fully processed. Mixing these states up can produce false positives.

Practical Tips for Graph Problems

• Draw diagrams to visualise the graph structure; this greatly helps in understanding the traversal your function needs to follow clearly.
• Keep track of node states explicitly and consistently.
• Always test for both positive and negative cases (with and without cycles).

Wrapping Up

Key Takeaways

• The Course Schedule problem checks for cycles within graph structures.
• Using DFS and tracking nodes carefully allows quick detection of cycles.
• Testing is crucial to ensure the solution correctly identifies cycles and non‑cycles.
• Clearly tracking visited and recursion states prevents mistakes.

The implementation in this article uses depth‑first search with visiting states. Encountering a course already on the current recursion path reveals a cycle; completing a course marks it safe for later traversals. If every traversal completes without finding a cycle, the schedule is possible.