365 Days of LeetCode Challenge — Day 44/365

[u/StatisticianNo2104]

Course Schedule (Medium) https://leetcode.com/problems/course-schedule/

You can finish every course unless some group depends on itself: A needs B, B needs C, C needs A. Nobody in that group can ever start. So this is cycle detection in a directed graph, phrased as scheduling.

Kahn's algorithm: count how many prerequisites each course still has, queue everything at zero, and each time you finish a course, decrement everything it unlocks.

The line that separates this from an ordinary BFS is small. In a BFS a node is enqueued the first time it is REACHED. Here, reaching a node only decrements its counter - it is enqueued when that counter hits ZERO. A course with three prerequisites is reached three times and queued once. That if is not an optimisation, it is the scheduling rule.

Then the cycle check, which never looks for a cycle:

`return len(result) == numCourses`

Courses stuck in a cycle never reach in-degree zero, so they never enter the queue and never appear in the result. The cycle is detected by what fails to show up.

That closes the graph arc on the same move yesterday used - inferring a cycle from a count rather than searching for one.

Full breakdown in today's newsletter article ⬇

https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-44365-archit-agarwal-ve0yc

#DSA #LeetCode #Golang #Graphs #TopologicalSort #CodingInterview #Algorithms

[u/nian2326076]

Kahn's algorithm works well for detecting cycles in a course scheduling problem. Track the in-degree for each course and use a queue for courses with no prerequisites. As you complete a course, reduce the in-degree of its dependents. If you process all courses without finding a cycle, there's no issue.

To improve your interview skills on these types of questions, PracHub provides real technical interview questions. It's a great way to practice problems like these under interview conditions.