Course Schedule is one of the most important Topological Sort interview problems.

You are given:

numCoursesprerequisites[][]

Goal:

Determine whether all courses can be completed.

A prerequisite:

[a,b] means b → a

You must finish:

b before a

Example 1

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

Output:

true 

Explanation:

 0 → 1Possible

Example 2

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

Output:

false 

Explanation:

0 → 11 → 0
Cycle Exists

Key Observation

If the graph contains:

Cycle

then:

All courses can be completed.

If graph has:

No Cycle

then:

All courses can be completed. 

What is Topological Sort?

Topological Sort is:

A valid ordering of vertices in a Directed Acyclic Graph. 

Example:

0 → 1 → 2 → 3 

Valid Order:

0 1 2 3 

Kahn's Algorithm

We use:

BFS 

and

Indegree Array 

Indegree means:

Number of incoming edges. 

Algorithm

1. Build graph.
2. Compute indegree.
3. Push indegree 0 nodes.
4. Perform BFS.
5. Remove edges.
6. Count processed nodes.
7. Compare with total courses. 

Dry Run

Input:

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

Graph:

0 → 1
↓
2
1 → 3
2 → 3 

Indegree:

0 = 01 = 1
2 = 1
3 = 2

Queue:

[0] 

Process:

0
↓
1,2
↓
3 

Visited:

4 nodes 

Answer:

true 

Approach : Topological Sort (Kahn's Algorithm)

Explanation

For every course:

1. Build dependency graph.
2. Track indegrees.
3. Start BFS from indegree 0 nodes.
4. Reduce indegrees.
5. Process all possible courses.
6. Check if every course is completed.

Practice

Topological Sort (Kahn's Algorithm)Time Complexity: O(V + E)
Space Complexity: O(V + E)

If all vertices are processed
→ No Cycle
Else
→ Cycle Exists