This problem requires detecting cycles in a course prerequisite graph to see if all courses are finishable. By computing indegrees and using a queue-driven topological sort, you can efficiently traverse courses in dependency order. A non-empty queue that processes all nodes confirms no blocking cycles exist, guaranteeing course completion.
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.
How GhostInterview Helps
- Capture the input graph visually or via screenshot to identify dependencies and zero indegree courses before processing.
- Provide a step-by-step answer path including indegree updates, queue operations, and cycle detection, with complexity clearly explained for each step.
- Support live screen-share workflows or captured layers so users can trace the topological sort and see exactly why cycles block course completion.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Course Schedule instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Course Schedule from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.