23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection)

50 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection)

> DSA Blind 75 Notes by Rishabh - Topic 23

---

### 1. Topological Sort & DAGs (Directed Acyclic Graphs 🎓)

Topological Sort graph ke directed nodes ka linear ordering hota hai jisme har edge $u \rightarrow v$ ke liye $u$ hamesha $v$ se pehle aata hai:
> **Strict Rule:** Topological Sort **SIRF Directed Acyclic Graphs (DAG)** par possible hota hai (Cycle aate hi topo sort fail ho jata hai!).

---

### 2. Kahn's Algorithm (BFS In-Degree Technique 👑)

1. Har node ki **In-Degree** (Incoming edges count) calculate karo.
2. Jin nodes ki In-Degree **0** hai, unhe Queue me daalo.
3. Queue se pop karo, result me jodo, aur uske neighbors ki In-Degree 1 kam karo.
4. Agar kisi neighbor ki In-Degree 0 ho jaye, use Queue me daalo.

```python
from collections import deque, defaultdict

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    in_degree = [0] * numCourses
    adj = defaultdict(list)
    
    for crs, pre in prerequisites:
        adj[pre].append(crs)
        in_degree[crs] += 1
        
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    completed_courses = 0
    
    while queue:
        node = queue.popleft()
        completed_courses += 1
        
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    return completed_courses == numCourses # True if No Cycle!
```

---

### 3. Master Comparison Matrix

| Algorithm | Mechanism | Cycle Detection | Complexity |
| :--- | :--- | :--- | :--- |
| **Kahn's (BFS)** | In-Degree Array + Queue | `count != numCourses` | ⚡ $O(V + E) / O(V + E)$ |
| **Tarjan's / DFS** | 3-Color State (`UNVISITED`, `VISITING`, `VISITED`) | Back-edge to `VISITING` node | ⚡ $O(V + E) / O(V + E)$ |

---

### 4. Interview Ke 3 Sawal Is Topic Se

1. **Course Schedule II (LeetCode #210) me valid course order kaise return hota hai?** -> Kahn's algorithm me pop hone wale nodes ka order array return karo; agar cycle detect ho toh empty `[]` return karo.
2. **Alien Dictionary (LeetCode #269 Hard) me Graph edges kaise construct hoti hain?** -> Consecutive sorted words ke pehle differing character se directed edge $c_1 \rightarrow c_2$ banayi jaati hai fir Topo Sort lagaya jata hai.
3. **Build Systems (Webpack, Make, Dockerfile layers) me Topological Sort kaise use hota hai?** -> Package dependency graph resolve karne ke liye taaki base libraries hamesha dependent modules se pehle compile hon.

---
**Next Topic:** 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                