LeetCode 207. Course Schedule

December 28, 2024

Today I worked on a general graph problem. My initial solution was much more verbose and less readable than another coder's solution. However, I feel like during an interview I would have been able to derive the simpler solution through asking questions, such as whether any course number will exceed the numCourses variable. I also need to be more mindful of what data I need to track or else I create unnecessary classes.

My Solution

Copy
1class Node:
2    def __init__(self, val: int, toNodes: List['Node'] = None, fromNodes: List['Node'] = None):
3        self.val = val
4        self.toNodes = toNodes if toNodes is not None else []
5        self.fromNodes = fromNodes if fromNodes is not None else []
6
7class Solution:
8    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
9        if not prerequisites:
10            return True
11
12        nodes = {}
13        for after, before in prerequisites:
14            if after not in nodes:
15                nodes[after] = Node(after)
16            afterNode = nodes[after]
17
18            if before not in nodes:
19                nodes[before] = Node(before)
20            beforeNode = nodes[before]
21            beforeNode.toNodes.append(afterNode)
22            afterNode.fromNodes.append(beforeNode)
23        
24        topological_order = []
25        stack = set()
26        visited = set()
27        has_cycle = False
28        def dfs(node):
29            nonlocal has_cycle
30            if node in stack:
31                return False
32            if node in visited:
33                return True
34            
35            stack.add(node)
36            print(node.val)
37            for child in node.toNodes:
38                if not dfs(child):
39                    has_cycle = True
40            stack.remove(node)
41            visited.add(node)
42            topological_order.append(node.val)
43            return True
44        
45        for node in nodes.values():
46            #if not node.fromNodes:
47            dfs(node)
48            if has_cycle:
49                return False
50
51        return len(topological_order) <= numCourses

The time complexity is O(M + N) where M are the number of nodes and N are the number of edges, as each are visited once. The space complexity is the same as it grows linearly with the input size. I used a class to build a directed graph which I could use to attempt a topological sort, this sort would allow me to check if there are less courses than numCourses and also detect cycles. However, the problem states numCourses is always less than the course numbers, we could instead check each course if we may satisfy it's given prerequisites up to numCourses. By default, we can say a course doesn't have any prerequisites. Therefor, we only need to check if there is ever a cycle, which we can detect using a set that tracks which courses we've taken.

If we can go through every course up to numCourses without visiting a taken class, we can return true. The topological order is unnecessary, however, it is given that a topological order exists if we can complete the courses.

Improved Solution

Copy
1class Solution:
2    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3        from collections import defaultdict
4
5        pres = defaultdict(list)
6        for course, pre in prerequisites:
7            pres[course].append(pre)
8        
9        taken = set()
10        def dfs(course):
11            if not pres[course]:
12                return True
13            
14            if course in taken:
15                return False # Cycle detected
16            
17            taken.add(course)
18            for pre in pres[course]:
19                if not dfs(pre):
20                    return False
21            
22            pres[course] = []
23            return True
24        
25        for course in range(numCourses):
26            if not dfs(course):
27                return False
28        
29        return True

LeetCode 22. Generate Parentheses

LeetCode 34. Find First and Last Position of Element in Sorted Array