🎯 CODING CHALLENGE #8 - Course Schedule (Detect Cycle in a Graph)
Difficulty: Medium-Hard | Asked at: Google, Meta, Uber

You have numCourses courses, and a list of prerequisite pairs [a, b] meaning "to take course a, you must first take course b." Determine if it's possible to finish all courses (i.e., there's no cyclic dependency).

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

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false   (cycle: 0 needs 1, 1 needs 0)

💡 Hint: This is cycle detection in a directed graph. Topological sort (Kahn's algorithm using in-degrees) is the cleanest approach.

Solution:

python
from collections import deque

def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    completed = 0

    while queue:
        node = queue.popleft()
        completed += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return completed == num_courses

Complexity: O(V + E) time and space, where V is courses and E is prerequisite pairs.

Common mistake: Trying to solve this with plain DFS + a visited set, without tracking the CURRENT recursion path separately. You need to distinguish "visited overall" from "visited in this current path" - otherwise you can't actually detect a cycle, only whether a node's been seen at all.

This "can this graph be finished/ordered" pattern (topological sort) shows up under many disguises - build systems, task scheduling, spreadsheet formula dependencies. Recognize the shape and you'll spot it fast.

Kahn's algorithm or DFS-based cycle detection - which do you find more intuitive? 👇