Problem Overview

You are given an integer numCourses representing the total number of courses labeled from 0 to numCourses - 1. You are also given an array prerequisites, where each element prerequisites[i] = [a, b] indicates that you must take course b before course a.

Return true if it is possible to finish all courses, otherwise return false.

This problem is essentially about detecting whether there exists a cycle in a directed graph. If there is a cycle, then some courses depend on each other circularly, making it impossible to finish them all.

Example 1:
Input:
numCourses = 2, prerequisites = [[1, 0]]
Output:
true
Explanation: You can take course 0 first, then course 1.

Example 2:
Input:
numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output:
false
Explanation: There is a cycle between course 0 and 1, so it’s impossible to finish both.

---

Intuition / Approach

This problem can be visualized as a directed graph, where:

• Each node represents a course.
• Each directed edge b → a represents a dependency (you must take b before a).

To determine if it’s possible to complete all courses, we must ensure there are no cycles in this dependency graph.
If a cycle exists, some courses depend on each other circularly, making it impossible to complete them.

There are two common ways to solve this:

1. Kahn’s Algorithm (BFS approach using indegree):
   Use topological sorting with indegrees.
   If all courses can be sorted topologically (i.e., we can visit all nodes), there’s no cycle.
   Otherwise, a cycle exists.
2. DFS with Cycle Detection:
   Use depth-first search to detect cycles by marking nodes during recursion.
   If we visit a node that is already in the current recursion path, a cycle is present.

Both approaches are valid. The BFS (Kahn’s algorithm) is often easier to reason about for this problem, so we’ll use it here.

---

Algorithm Explanation (Using BFS / Topological Sort)

1. Build the graph representation:
   • Create an adjacency list for numCourses nodes.
   • For every pair [a, b] in prerequisites, add b → a to the adjacency list.
   • Maintain an array indegree where indegree[i] represents how many prerequisites course i has.
2. Initialize the queue:
   • Add all courses with indegree = 0 (i.e., no prerequisites) to the queue — they can be taken first.
3. Process the queue:
   • While the queue is not empty:
     • Remove a course from the queue.
     • Increment a counter for the number of courses taken.
     • For each course dependent on this one, decrement its indegree.
     • If any course’s indegree becomes 0, add it to the queue.
4. Check completion:
   • After processing all courses, if the number of courses taken equals numCourses, return true.
   • Otherwise, return false (a cycle prevented completing all courses).

---

Java Code Implementation

import java.util.*;

public class CourseSchedule {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Step 1: Create adjacency list and indegree array
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        int[] indegree = new int[numCourses];

        // Step 2: Build graph and compute indegrees
        for (int[] pre : prerequisites) {
            int course = pre[0];
            int prerequisite = pre[1];
            graph.get(prerequisite).add(course);
            indegree[course]++;
        }

        // Step 3: Initialize queue with courses having indegree 0
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // Step 4: Process courses in BFS manner
        int completedCourses = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            completedCourses++;

            // Reduce indegree of dependent courses
            for (int nextCourse : graph.get(current)) {
                indegree[nextCourse]--;
                if (indegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }

        // Step 5: Check if all courses can be completed
        return completedCourses == numCourses;
    }

    // Optional main method for testing
    public static void main(String[] args) {
        CourseSchedule cs = new CourseSchedule();
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}};
        System.out.println(cs.canFinish(numCourses, prerequisites)); // true

        int[][] prerequisites2 = {{1, 0}, {0, 1}};
        System.out.println(cs.canFinish(2, prerequisites2)); // false
    }
}

---

Dry Run Example

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

1. Graph representation:
   • 0 → [1]
   • 1 → [2]
   • 2 → [3]
   • 3 → []
2. Indegree array:
   • [0, 1, 1, 1]
3. Initialize queue with courses having indegree = 0:
   Queue = [0]
4. Process:
   • Take course 0 → reduce indegree of 1 → now indegree[1] = 0 → enqueue 1
   • Take course 1 → reduce indegree of 2 → now indegree[2] = 0 → enqueue 2
   • Take course 2 → reduce indegree of 3 → now indegree[3] = 0 → enqueue 3
   • Take course 3 → no dependents

All 4 courses taken → return true.

---

Complexity Analysis

• Time Complexity:
  O(V + E) where V = number of courses, E = number of prerequisite relations.
  Building the graph and processing each edge and node once leads to linear complexity.
• Space Complexity:
  O(V + E)
  Space used for adjacency list, indegree array, and queue.

---

Alternative Approach: DFS with Cycle Detection

In the DFS approach:

1. Represent the courses as a graph.
2. Maintain a recursion stack (visited path).
3. For each node:
   • Mark it as visiting.
   • Recurse on its neighbors.
   • If a neighbor is already marked as visiting, a cycle exists.
   • Once finished, mark it as visited.

This approach also detects cycles but uses recursion instead of an explicit queue.
Time and space complexities are the same, though the BFS approach is often more intuitive for this specific problem.

---

Final Thoughts

This problem is a classic example of topological sorting in a directed acyclic graph (DAG).
The main insight is recognizing that “finishing all courses” is equivalent to being able to produce a valid topological order.

• If a topological order exists → all courses can be finished → no cycle.
• If no such order exists → a cycle is present → impossible to complete all courses.

Understanding this concept helps in solving other dependency-related problems, such as task scheduling, build systems, or resolving module dependencies in compilers.