Leetcode 207. Course Schedule

Let's understand what we're being asked to do. We have courses represented as nodes and prerequisite relationships as directed edges. For example, if course 1 requires course 0 as a prerequisite, we have an edge from 0 to 1.

Given numCourses = 2 and prerequisites = [[1,0]], this means course 1 depends on course 0. We can complete course 0 first, then course 1, so return true.

But consider numCourses = 2 and prerequisites = [[1,0],[0,1]]. Course 1 requires course 0, AND course 0 requires course 1. This creates a circular dependency - we can't complete either course! Return false.

Key constraint: We need to determine if a valid ordering exists where all prerequisites are satisfied before taking a course.

Edge cases to consider: What if there are no prerequisites at all? (all courses can be completed). What if a course has no prerequisites but other courses depend on it? What if there are multiple disconnected components in the graph?

Use depth-first search with cycle detection. For each course, recursively visit all its prerequisites, marking nodes as 'visiting' during traversal and 'visited' after completion. If we encounter a node marked 'visiting' during recursion, we've found a cycle. This approach explores all paths but may revisit nodes multiple times, making it less efficient than the optimal solution.

A course can only be completed if all its prerequisites are completed first. This means we need to process courses in an order where dependencies come before dependents.

The critical insight: if there's a cycle in the dependency graph (course A requires B, B requires C, C requires A), then no valid ordering exists because we'd need to complete A before starting A!

This transforms the problem from 'can we complete all courses?' to 'does the directed graph have a cycle?'

If the graph is acyclic (no cycles), we can find a topological ordering - a linear arrangement where all edges point forward. If there's a cycle, no such ordering exists.

Think about getting dressed in the morning. You must put on socks before shoes, underwear before pants. These are dependencies that form a directed graph.

If the rules were: 'put on shoes before socks' AND 'put on socks before shoes', you'd have a circular dependency - impossible to satisfy! But if the dependencies form a tree-like structure with no cycles, you can find a valid order to get dressed.

Use Kahn's algorithm for topological sorting with BFS. First, calculate the in-degree (number of prerequisites) for each course. Start with courses that have zero in-degree (no prerequisites) and add them to a queue. Process each course by removing it from the queue and decreasing the in-degree of all courses that depend on it. If a course's in-degree becomes zero, add it to the queue. If we process all courses, the graph is acyclic; otherwise, a cycle exists.

• Cycle detection via topological sort: When a problem asks if tasks with dependencies can be completed or if an ordering exists, recognize this as a directed acyclic graph (DAG) verification problem - use either Kahn's algorithm (BFS with in-degree tracking) or DFS with coloring to detect cycles, as cycles make topological ordering impossible.
• In-degree tracking pattern: Build an in-degree array counting incoming edges for each node, then use a queue initialized with all zero in-degree nodes - as you process nodes, decrement in-degrees of neighbors and add newly zero in-degree nodes to the queue; if you process all nodes, no cycle exists.
• Adjacency list construction: Convert the prerequisite pairs into an adjacency list representation (HashMap or array of lists) rather than using an adjacency matrix - this gives O(V + E) space instead of O(V²) and allows efficient neighbor iteration, critical when edges are sparse relative to possible connections.
• Three-state DFS coloring: For the DFS approach, use three states (unvisited, visiting, visited) to track node status - if you encounter a node in the 'visiting' state during DFS, you've found a back edge indicating a cycle; this is more reliable than just tracking visited nodes which can miss cycles in disconnected components.
• Complete traversal verification: A critical mistake is assuming no cycle exists just because DFS/BFS completes - you must verify that all N nodes were processed (count == numCourses in BFS, or all nodes marked visited in DFS), as disconnected components with cycles might be missed if you only start from one node.
• Dependency resolution systems: This pattern appears in build systems (Maven, Gradle), package managers (npm, pip), task schedulers, and database transaction ordering - any system where operations have prerequisites needs cycle detection to ensure valid execution order and prevent deadlocks.