Course Schedule
Problem link: https://leetcode.com/problems/course-schedule/
Problem Statement
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a. Return true if you can finish all courses. Otherwise, return false.
Input
An integer numCourses and a 2D integer array prerequisites.
Output
A boolean indicating if it is possible to complete all courses.
Example
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Explanation
The prerequisites represent a directed graph. In this case, there is a path from 0 to 1 with no cycles, so we can complete course 0 and then course 1.
Brute Force
Intuition
Try all possible permutations of courses and check if any permutation satisfies the prerequisite conditions. If any valid ordering exists, return true.
Approach
- Generate all
n!permutations of courses. - For each permutation, check if every course appears after its prerequisites.
- Return true if a valid permutation is found.
Dry Run
numCourses = 2, prereq = [[1,0]] Permutations: [0, 1] (Valid), [1, 0] (Invalid). Result: true
Code (Java)
// Omitted due to extreme inefficiency (O(N! * P))
Complexity Analysis
Generating all permutations takes factorial time, and checking each one takes time proportional to the number of prerequisites.
Optimal Solution
Intuition
This is a cycle detection problem in a directed graph. If the graph contains a cycle, it's impossible to finish all courses. We can use Kahn's Algorithm (BFS) to find a topological sort. If we can process all courses, there's no cycle.
Approach
- Build an adjacency list and an in-degree array for the graph.
- Add all courses with in-degree 0 to a queue.
- While the queue is not empty:
- Poll a course, increment the
countof completed courses. - For each neighbor, decrement its in-degree.
- If a neighbor's in-degree becomes 0, add it to the queue.
- Poll a course, increment the
- If
count == numCourses, return true.
Dry Run
numCourses = 2, prereq = [[1,0], [0,1]]
- In-degrees: [1:1, 0:1]
- Queue is empty (no 0 in-degree).
- Count (0) != numCourses (2). Result: false (Cycle detected)
Code (Java)
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.add(i);
}
int count = 0;
while (!q.isEmpty()) {
int curr = q.poll();
count++;
for (int next : adj.get(curr)) {
if (--indegree[next] == 0) q.add(next);
}
}
return count == numCourses;
}
}
Complexity Analysis
We traverse every node (V) and every edge (E) exactly once. Space is required for the adjacency list and queue.
Quick Revision (Brute Force)
- Check all permutations
- Factorial time complexity
- Impractical for large N
Quick Revision (Optimal)
- Kahn's Algorithm (BFS Topological Sort)
- Cycle detection in directed graph
- In-degree array + Queue
- O(V + E) time and space