#207

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Course Schedule

Determine if all courses can be completed by analyzing prerequisite dependencies using indegree tracking and topological sorting to detect cycles.

graph topological sort breadth first search queue

Problem Statement

You are given a total number of courses labeled from 0 to numCourses - 1 and a list of prerequisite pairs where each pair [a, b] indicates you must complete course b before course a. Your task is to decide if it is possible to finish all courses by respecting the prerequisite constraints, ensuring no course is attempted before its dependencies are completed.

The schedule can fail only if the prerequisite graph contains a cycle that prevents a course from becoming available. Your goal is to return true if all courses can be completed in some valid order or false if a dependency cycle blocks progress. Constraints guarantee up to 2000 courses and 5000 prerequisite pairs, making efficient graph traversal essential.

Examples

Example 1

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

Output: true

Course 0 has no prerequisites, so you can take it first and then unlock course 1. The graph has no cycle.

Example 2

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

Output: false

Each course depends on the other, so neither can become available first. The dependency graph contains a cycle.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
Each prerequisite pair has exactly two integers.
The decision depends on whether every course can be reached in an order that respects dependencies.

Solution Approach

Build the Graph and Compute Indegrees

First, construct an adjacency list representing the prerequisite relationships and an array to track the indegree of each course. Each course starts with indegree zero, then increment the indegree for courses that depend on others. This setup identifies which courses are ready to be taken first, directly reflecting the pattern of indegree tracking used in topological sorting for cycle detection.

Topological Traversal Using a Queue

Initialize a queue with all courses that have zero indegree, meaning they have no prerequisites. Iteratively remove courses from the queue, decrement the indegree of dependent courses, and enqueue any that reach zero indegree. This queue-driven traversal ensures courses are taken in a valid order while naturally revealing cycles when some nodes remain with non-zero indegree after processing.

Cycle Detection and Completion Decision

After processing all possible courses through the queue, check if any course still has a non-zero indegree. Remaining indegrees indicate a cycle in the dependency graph, which prevents completion of all courses. If all indegrees reach zero, it confirms a topological ordering exists and every course can be completed. This step directly links the failure mode of the problem to blocking cycles.

Complexity Analysis

Metric	Value
Time	O(V + E)
Space	O(V + E)

Building the graph and computing indegrees requires O(V + E) time and space, where V is numCourses and E is the number of prerequisites. Traversing the graph via the queue-driven topological sort also takes O(V + E) time. Overall, both the time and space complexity are O(V + E), ensuring efficient handling of large course and prerequisite counts.

What Interviewers Usually Probe

Do you handle cases where the graph contains cycles preventing course completion?
Can you implement the topological ordering using indegree tracking and a queue efficiently?
Will you verify that every course reaches zero indegree after processing to confirm completion?

Common Pitfalls or Variants

Common pitfalls

Forgetting to initialize the indegree array correctly, which can lead to missing courses that should start with zero indegree.
Modifying the queue or indegree counts incorrectly, causing false detection of cycles or skipping courses that should be processed.
Assuming that courses with zero prerequisites at the start always guarantee completion without checking the entire graph for hidden cycles.

Follow-up variants

Return a valid ordering of courses if possible, not just a boolean indicating completion.
Determine the minimum number of semesters needed to finish all courses given that multiple courses can be taken simultaneously if prerequisites allow.
Handle a dynamic list of prerequisites where courses can be added or removed, and check completion feasibility incrementally.

FAQ

How do I know if the Course Schedule problem has a cycle?

By building the adjacency list and tracking indegrees, if any course remains with non-zero indegree after processing, a cycle exists and prevents completion.

Can I solve Course Schedule without a queue?

Yes, a depth-first search can also detect cycles, but the queue-based topological sort using indegree is more intuitive and directly shows available courses.

What is the main failure mode in Course Schedule?

The schedule fails only when a cycle exists in the prerequisite graph, preventing one or more courses from ever becoming available for completion.

How do I efficiently track dependencies between courses?

Use an adjacency list to represent the graph and an indegree array to track how many prerequisites each course has, updating these values during traversal.

What happens if numCourses is large but prerequisites are few?

The algorithm still runs efficiently because it only processes edges and nodes with relevant dependencies, maintaining O(V + E) time and space complexity even with sparse graphs.

terminal

Solution

Solution 1: Topological Sorting

For this problem, we can consider the courses as nodes in a graph, and prerequisites as edges in the graph. Thus, we can transform this problem into determining whether there is a cycle in the directed graph.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            g[b].append(a)
            indeg[a] += 1
        q = [i for i, x in enumerate(indeg) if x == 0]
        for i in q:
            numCourses -= 1
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return numCourses == 0

Continue Practicing

#206 reverse linked list #1 two sum