207: Course Schedule (qiyuangong#57)

dannysepler · web-flow · commit 250a8c7c7577 · 2022-06-23T08:39:07.000+08:00
* Add 207_Course_Schedule.py, detect cycle Contributed by @dannysepler
diff --git a/README.md b/README.md
@@ -86,6 +86,7 @@ I'm currently working on [Analytics-Zoo](https://github.com/intel-analytics/anal
 | 200 | [Number of Islands](https://leetcode.com/problems/number-of-islands/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/200_Number_of_Islands.py) | 1. Quick union find, O(nlogn) and O(n^2)<br>2. BFS with marks, O(n^2) and O(1) |
 | 204 | [Count Primes](https://leetcode.com/problems/count-primes/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/204_Count_Primes.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/204_Count_Primes.java) [CPP](https://github.com/qiyuangong/leetcode/blob/master/cpp/204_Count_Primes.cpp) | [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity), O(nloglogn) and O(n) |
 | 206 | [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/206_Reverse_Linked_List.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/206_Reverse_Linked_List.java) [CPP](https://github.com/qiyuangong/leetcode/blob/master/cpp/206_Reverse_Linked_List.cpp) | 1. Stack, O(n) and O(n)<br>2. Traverse on prev and curr, then curr.next = prev, O(n) and O(1)<br>3. Recursion, O(n) and O(1) |
+| 207 | [Course Schedule](https://leetcode.com/problems/course-schedule/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/207_Course_Schedule.py) | Cycle detection problem |
 | 213 | [House Robber II](https://leetcode.com/problems/house-robber-ii/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/213_House_Robber_II.py) | f(k) = max(f(k – 2) + num[k], max(dp[0~ls-2],dp[1~ls-1], O(n) and O(1)|
 | 215 | [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/215_Kth_Largest_Element_in_an_Array.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/215_Kth_Largest_Element_in_an_Array.java) | 1. Sort, O(n) and O(n)<br>2. Heap, O(nlgk) and O(n)<br>3. Quick selection, O(klgn) and O(n)|
 | 216 | [Combination Sum III](https://leetcode.com/problems/combination-sum-iii/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/216_Combination_Sum_III.py) | Generate all combinations of length k and keep those that sum to n|
diff --git a/python/207_Course_Schedule.py b/python/207_Course_Schedule.py
@@ -0,0 +1,28 @@
+from collections import defaultdict
+
+class Solution(object):
+    # Adapted from https://youtu.be/yPldqMtg-So
+
+    def hasCycle(self, course, deps, visited, tracker):
+        visited.add(course)
+        tracker.add(course)
+        for n in deps[course]:
+            if n not in visited and self.hasCycle(n, deps, visited, tracker):
+                return True
+            if n in tracker:
+                return True
+        tracker.remove(course)
+        return False
+
+    def canFinish(self, numCourses, prerequisites):
+        deps = defaultdict(set)
+        for course, pre in prerequisites:
+            deps[pre].add(course)
+
+        visited = set()
+        for course in range(numCourses):
+            tracker = set()
+            if self.hasCycle(course, deps, visited, tracker):
+                return False
+        
+        return True
