Can All Courses Be Completed?
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Can All Courses Be Completed?
You are enrolling in a program with `numCourses` courses, labeled `0` to `numCourses - 1`. Some courses have prerequisites: you are given a list `prerequisites` where each entry `[a, b]` means **you must finish course `b` before you can take course `a`**.
Determine whether it is possible to finish **all** of the courses. Return `true` if there is some ordering in which every course can be taken (respecting all prerequisites), and `false` otherwise.
### Example 1
```
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
```
To take course `1` you must first take course `0`. The order `0, 1` works, so all courses can be finished.
### Example 2
```
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
```
Course `1` requires course `0`, and course `0` requires course `1`. This is a circular dependency, so no valid ordering exists.
### Example 3
```
Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: true
```
One valid order is `0, 1, 2, 3`.
### Constraints
- `1 <= numCourses <= 2000`
- `0 <= prerequisites.length <= 5000`
- `prerequisites[i].length == 2`
- `0 <= a, b < numCourses`
- All prerequisite pairs `[a, b]` are distinct.
### Required Output
Return a boolean: `true` if all courses can be completed, `false` if any circular dependency makes that impossible.
Quick Answer: This question tests graph traversal and cycle detection skills, specifically the ability to model dependency relationships as a directed graph. It evaluates practical understanding of topological sorting and its application to constraint-satisfaction problems, a core concept in algorithms interviews for software engineering roles.
You are enrolling in a program with `numCourses` courses, labeled `0` to `numCourses - 1`. Some courses have prerequisites: you are given a list `prerequisites` where each entry `[a, b]` means **you must finish course `b` before you can take course `a`**.
Determine whether it is possible to finish **all** of the courses. Return `true` if there is some ordering in which every course can be taken (respecting all prerequisites), and `false` otherwise.
### Example 1
```
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
```
To take course `1` you must first take course `0`. The order `0, 1` works, so all courses can be finished.
### Example 2
```
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
```
Course `1` requires course `0`, and course `0` requires course `1`. This is a circular dependency, so no valid ordering exists.
### Example 3
```
Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: true
```
One valid order is `0, 1, 2, 3`.
This is the classic "Course Schedule" problem: model courses as nodes in a directed graph where an edge `b -> a` means `b` must come before `a`. All courses can be completed if and only if the graph has no directed cycle (i.e., a valid topological ordering exists).
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= a, b < numCourses
- All prerequisite pairs [a, b] are distinct.
Examples
Input: (2, [[1, 0]])
Expected Output: True
Explanation: Take course 0 first, then course 1. Valid order exists.
Input: (2, [[1, 0], [0, 1]])
Expected Output: False
Explanation: 0 requires 1 and 1 requires 0 — a 2-node cycle, so no ordering works.
Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])
Expected Output: True
Explanation: Order 0, 1, 2, 3 respects every prerequisite.
Input: (1, [])
Expected Output: True
Explanation: A single course with no prerequisites can always be completed.
Input: (3, [[0, 1], [1, 2], [2, 0]])
Expected Output: False
Explanation: 0->1->2->0 forms a directed cycle, so finishing all courses is impossible.
Input: (5, [])
Expected Output: True
Explanation: No prerequisites at all — every course is independent and can be taken in any order.
Input: (3, [[1, 0], [2, 1]])
Expected Output: True
Explanation: A linear chain 0 -> 1 -> 2; the order 0, 1, 2 finishes everything.
Hints
- Model each course as a node in a directed graph. An entry [a, b] means an edge from b to a (b must be taken before a).
- All courses can be finished if and only if the graph contains no directed cycle — equivalently, a valid topological order exists.
- Kahn's algorithm: repeatedly remove nodes with in-degree 0. If you can remove all numCourses nodes this way, there is no cycle; otherwise a cycle remains.
- Alternatively, run DFS and detect a back edge (a node revisited while still in the current recursion stack) to find a cycle.