Find whether it is possible to finish all tasks or not from given dependencies
Problem Statement
There are numCourses courses labeled 0 to numCourses-1. You are given prerequisite pairs where [a, b] means you must take course b before course a. Determine if it is possible to finish all courses (i.e., check if the course schedule is valid).
Example:
-
Input:
numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]] -
Output:
true(Take courses in order: 0 → 1 → 2 → 3) -
Input:
numCourses = 2, prerequisites = [[1,0],[0,1]] -
Output:
false(Circular dependency: 0 needs 1, 1 needs 0)
Noob-Friendly Explanation
Imagine you're in college and some courses have prerequisites. You can't take "Data Structures" without first taking "Intro to Programming." Can you plan a schedule to take ALL courses?
The answer is NO if there's a circular dependency (A needs B, B needs C, C needs A — nobody can go first). This is the same as detecting a cycle in a directed graph. If there's no cycle, you can finish all courses.
Approach 1: Brute Force (DFS Cycle Detection)
Intuition
Model courses as a directed graph. Use DFS with a recursion stack to detect cycles. If a cycle exists, return false (can't finish all tasks).
Algorithm
- Build a directed graph from prerequisites.
- Use DFS with visited and recStack arrays.
- If any cycle is detected, return false.
- If no cycle, return true.
import java.util.ArrayList;
import java.util.List;
public class CourseScheduleDFS {
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]); // pre[1] must come before pre[0]
}
boolean[] visited = new boolean[numCourses];
boolean[] recStack = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (hasCycle(adj, visited, recStack, i)) {
return false;
}
}
}
return true;
}
static boolean hasCycle(List<List<Integer>> adj, boolean[] visited,
boolean[] recStack, int node) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : adj.get(node)) {
if (recStack[neighbor]) return true; // cycle
if (!visited[neighbor] && hasCycle(adj, visited, recStack, neighbor)) {
return true;
}
}
recStack[node] = false;
return false;
}
public static void main(String[] args) {
System.out.println(canFinish(4, new int[][]{{1,0},{2,1},{3,2}})); // true
System.out.println(canFinish(2, new int[][]{{1,0},{0,1}})); // false
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is visited once.
- Space Complexity: O(V + E) — for adjacency list, visited, recStack, and recursion stack.
Approach 2: Optimal (BFS — Kahn's Algorithm)
Intuition
Use topological sort via BFS. If we can process all vertices (all courses have been "taken"), there's no cycle, and we can finish all tasks. If some courses remain unprocessed, there's a circular dependency.
Algorithm
- Build adjacency list and compute in-degrees.
- Add all courses with in-degree 0 to a queue.
- Process queue: for each course, reduce in-degree of dependent courses.
- Count processed courses. If count equals numCourses, return true.
import java.util.*;
public class CourseScheduleBFS {
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int next : adj.get(course)) {
inDegree[next]--;
if (inDegree[next] == 0) {
queue.add(next);
}
}
}
return count == numCourses;
}
public static void main(String[] args) {
System.out.println(canFinish(4, new int[][]{{1,0},{2,1},{3,2}})); // true
System.out.println(canFinish(2, new int[][]{{1,0},{0,1}})); // false
}
}Complexity Analysis
- Time Complexity: O(V + E) — each course and prerequisite is processed once.
- Space Complexity: O(V) — for in-degree array and queue (adjacency list is O(V + E)).