Course Schedule: Detect a Cycle in Python and TypeScript

The Problem

There are a number of courses, labelled 0 to n - 1. Each prerequisite pair [course, before] means you must finish before first. Return true if it is possible to finish all the courses, and false if the prerequisites make it impossible.

Example 1

Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Why: take course 0, then course 1.

Example 2

Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Why: each course needs the other first, so neither can ever be started.

Assumptions to confirm

• Can a course list itself as a prerequisite? (Treat it as a cycle.)
• Can the same pair appear twice? (It does not change the answer.)
• Do you need the order, or only yes or no? (Only yes or no here. Producing the order is a topological sort.)

Start With the Brute Force

A brute force tries orderings of the courses and checks whether any one respects every prerequisite. With n courses there are n! orderings, so it is only useful to explain what "possible" means.

The key observation to say out loud: a valid order exists exactly when there is no loop of prerequisites, such as A needs B, B needs C and C needs A. That turns the question into cycle detection in a directed graph.

The Optimal Approach: Cycle Detection With DFS

Solution in Python and TypeScript

Both versions use the three states. The difference between visiting and done is what separates a real cycle from two paths that simply meet.

Python

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    for course, before in prerequisites:
        graph[before].append(course)  # edge: before -> course
    UNSEEN, VISITING, DONE = 0, 1, 2
    state = [UNSEEN] * num_courses

    def has_cycle(node: int) -> bool:
        state[node] = VISITING
        for nxt in graph[node]:
            if state[nxt] == VISITING:
                return True  # back edge: a loop of prerequisites
            if state[nxt] == UNSEEN and has_cycle(nxt):
                return True
        state[node] = DONE
        return False

    return not any(state[c] == UNSEEN and has_cycle(c) for c in range(num_courses))

TypeScript

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, before] of prerequisites) graph[before].push(course); // before -> course
  const UNSEEN = 0, VISITING = 1, DONE = 2;
  const state = new Array<number>(numCourses).fill(UNSEEN);

  const hasCycle = (node: number): boolean => {
    state[node] = VISITING;
    for (const next of graph[node]) {
      if (state[next] === VISITING) return true; // back edge: a loop of prerequisites
      if (state[next] === UNSEEN && hasCycle(next)) return true;
    }
    state[node] = DONE;
    return false;
  };

  for (let c = 0; c < numCourses; c++) {
    if (state[c] === UNSEEN && hasCycle(c)) return false;
  }
  return true;
}

Kahn's algorithm, which repeatedly takes courses with no remaining prerequisites, answers the same question: if it processes every course, there is no cycle. It also produces an order. Both methods, with full code, are on the topological sort page.

For very deep prerequisite chains, recursive DFS can hit the recursion limit, especially in Python. Kahn's algorithm avoids recursion entirely.

Time and Space Complexity

How to Talk Through Course Schedule in an Interview

1. Clarify: "Do you only need yes or no, or the order as well? Can a course require itself?"
2. Brute force: "I could try every order, but that is factorial."
3. Optimise: "Courses and prerequisites form a directed graph. All courses can be finished exactly when there is no cycle, so I will detect cycles with DFS in linear time."
4. Code: explain the three states and why a node on the current path signals a cycle.
5. Test: the two examples, a three-course loop, and a diamond shape where two paths meet but there is no cycle. State O(V + E).

Edge Cases and Common Follow-Ups

Practise Course Schedule in a Mock Coding Round

Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Course Schedule out loud, under time pressure, while explaining each decision.

MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).

Frequently Asked Questions