Course Schedule

Link : 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] = [ai, bi] indicates that you must take course bi before course ai.

Return true if you can finish all courses. Otherwise, return false.

Example

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

Output:
true

Explanation:
You can take the courses in the order 0 → 1 → 2 → 3

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

Output:
false

Explanation:
A cycle is formed between 0 and 1. No valid order exists.

Constraints

• 1 <= numCourses <= 10^5

• 0 <= prerequisites.length <= 10^5

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• All prerequisite pairs are unique.

Intuition

The problem is equivalent to detecting a cycle in a directed graph. Each course is a node, and each prerequisite pair [a, b] means a directed edge from b → a.

• If there’s a cycle, it's impossible to complete all courses.

• If the graph is a Directed Acyclic Graph (DAG), you can finish all courses.

We can use Topological Sort to solve this.

Why Topological Sort?

• Topological Sort only exists for DAGs.

• If a valid topological ordering exists, the graph has no cycle → return true.

• If we cannot find such an ordering due to a cycle, we return false.

Approaches

Approach 1: BFS – Kahn’s Algorithm (Topological Sort)

Algorithm:

1. Build the graph using an adjacency list.

2. Calculate the in-degree (number of incoming edges) for each node.

3. Add all nodes with in-degree = 0 into a queue.

4. Perform BFS:

   • Remove a node from queue.

   • For each neighbor, reduce its in-degree.

   • If any neighbor’s in-degree becomes 0, add it to the queue.

5. Keep a count of visited nodes. If it's equal to numCourses, return true.

Code – Java (Kahn's Algorithm)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];

        for (int i = 0; i < numCourses; i++)
            graph.add(new ArrayList<>());

        for (int[] pre : prerequisites) {
            int u = pre[1];
            int v = pre[0];
            graph.get(u).add(v);
            inDegree[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)
                q.offer(i);
        }

        int count = 0;
        while (!q.isEmpty()) {
            int node = q.poll();
            count++;
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                    q.offer(neighbor);
            }
        }

        return count == numCourses;
    }
}

Dry Run

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

Adjacency list:

0 → 1  
1 → 2  
2 → 3  

In-degree: [0,1,1,1]

Queue starts with [0] → Remove 0 → Reduce in-degree of 1 → [1]
Remove 1 → Reduce in-degree of 2 → [2]
Remove 2 → Reduce in-degree of 3 → [3]
Remove 3 → No neighbors

Visited = 4 → Equals numCourses → Return true

Time and Space Complexity

• Time Complexity: O(N + E)

  • N = number of courses (nodes)

  • E = number of prerequisites (edges)

• Space Complexity: O(N + E)

  • Adjacency list + queue + in-degree array

Approach 2: DFS Cycle Detection (Alternate)

Use DFS to detect cycles in the directed graph:

• Mark nodes as:

  • 0 → Not visited

  • 1 → Visiting (part of current DFS stack)

  • 2 → Fully visited

• If you revisit a node with status 1, a cycle is detected.

Real-World Application

This type of scheduling is used in:

• Build systems (like Makefiles or compilers)

• Task scheduling with dependencies

• Course planning systems

Conclusion

• Use Topological Sort to determine if it's possible to complete all courses.

• The graph must be a DAG (no cycles).

• Both BFS (Kahn’s) and DFS (color-marking) are valid for cycle detection in directed graphs.