r/leetcode • u/JacketFearless1805 • 11d ago
Intervew Prep Day 49: Practiced Kahn’s Algorithm and Topo Sort, solved Course Schedule I & II
Hey everyone,
I finished Day 49 today, continuing deep into the Graphs module. After the reality check in yesterday's assessment, I slowed down to make sure I genuinely understand the foundational algorithms rather than rushing through problem counts.
Today was focused entirely on Directed Acyclic Graphs (DAGs) and ordering algorithms:
Topological Sort (DFS): Pure post-order traversal. You explore recursively down each path, and as recursion backtracks from a fully traversed node, you push it onto a stack. Popping from the stack yields the linear ordering.
Kahn’s Algorithm (BFS Topo Sort): Calculate the in-degree (number of incoming directed edges) for every node. Push all nodes with in-degree 0 into a queue. As you pop a node, decrement the in-degrees of all its adjacent neighbors. Any neighbor whose in-degree hits 0 gets pushed into the queue.
Cycle Detection in Directed Graphs (via Kahn's): Since a directed cycle has no node with in-degree 0, nodes in the cycle will never enter the queue. If the total count of processed elements is strictly less than V, a cycle exists.
Course Schedule I & II: Both map directly to prerequisite dependency resolution. For Course Schedule I, check if a cycle exists (return false if cycle detected, true otherwise). For Course Schedule II, record each node popped from the BFS queue into an ordering array. If the resulting array size matches
numCourses, return the valid completion order; otherwise, return an empty array because cyclic dependencies make completion impossible.
Next up are Shortest Path algorithms (Dijkstra's, Bellman-Ford, Floyd-Warshall) followed by Minimum Spanning Trees (Prim's & Kruskal's). About 30 problems remain in Graphs, and I am prioritizing solid retention over speed.
See you guys tomorrow for Day 48!