How do you solve Course Schedule on LeetCode?

Course Schedule (LeetCode #207) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + p) time complexity and O(n) space complexity. Key insight: Detecting cycles in a directed graph is crucial for solving this problem.

What is the brute force solution for Course Schedule?

The brute force approach for Course Schedule is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute-force approach involves checking all possible orders of taking courses to see if we can complete all of them. This is inefficient because it tries every combination, which can grow exponentially. The optimal Optimal Solution approach improves this to O(n + p).

What algorithm or data structure is used to solve Course Schedule?

Course Schedule uses the following concepts: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort. The recommended patterns to study are: Graph Theory, Topological Sort, Depth-First Search, Breadth-First Search.

What are the interview tips for Course Schedule?

Always clarify the problem and constraints before diving into coding. Think about edge cases, such as no prerequisites or all courses dependent on one. Practice explaining your thought process while coding, as communication is key in interviews.

What are common mistakes when solving Course Schedule?

Not recognizing that this problem is about cycle detection in graphs. Failing to account for all prerequisites when checking course orders.

#207

Course Schedule

Medium

Depth-First SearchBreadth-First SearchGraph TheoryTopological SortGraph TheoryTopological SortDepth-First SearchBreadth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n + p)
Space	O(n)	O(n)

💡

Intuition

Time O(n + p)Space O(n)

The optimal solution uses graph theory to detect cycles in a directed graph. If there is a cycle, it's impossible to complete all courses. We can use either Depth-First Search (DFS) or Kahn's Algorithm (BFS) for topological sorting to check for cycles.

⚙️

Algorithm

5 steps

1Step 1: Build a graph using an adjacency list from the prerequisites.
2Step 2: Maintain an array to track the in-degree of each course.
3Step 3: Use a queue to perform Kahn's algorithm: enqueue all courses with in-degree 0.
4Step 4: Dequeue a course, reduce the in-degree of its neighbors, and enqueue any that reach in-degree 0.
5Step 5: If all courses are processed, return true; otherwise, return false.

solution.py23 lines

1# Full working Python code
2from collections import deque
3
4def canFinish(numCourses, prerequisites):
5    graph = [[] for _ in range(numCourses)]
6    in_degree = [0] * numCourses
7    
8    for a, b in prerequisites:
9        graph[b].append(a)
10        in_degree[a] += 1
11    
12    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
13    count = 0
14    
15    while queue:
16        course = queue.popleft()
17        count += 1
18        for neighbor in graph[course]:
19            in_degree[neighbor] -= 1
20            if in_degree[neighbor] == 0:
21                queue.append(neighbor)
22    
23    return count == numCourses

ℹ

Complexity note: This complexity comes from building the graph and processing each course and prerequisite pair, where n is the number of courses and p is the number of prerequisite pairs.

1Detecting cycles in a directed graph is crucial for solving this problem.
2Topological sorting can be achieved using either DFS or BFS.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.