Prerequisite Check

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Prerequisite Check

A degree program has num_courses courses labeled 0 to num_courses - 1. Each pair [a, b] in prerequisites means course a requires finishing course b first.

Return True if it is possible to finish every course, or False if the requirements form a cycle.

def can_finish(num_courses, prerequisites):
    pass

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 25-30 mins
🛠️ Topics: Graphs, Topological Sort, Cycle Detection

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: What does a pair [a, b] in prerequisites represent?
- A: Course a requires finishing course b first, i.e. there is a dependency edge from b to a in the course graph.
Q: When is it impossible to finish every course?
- A: When the prerequisites form a cycle (e.g. course 0 requires course 1 and course 1 requires course 0), no course in the cycle can ever be started.
Q: Can a course have no prerequisites at all?
- A: Yes. Any course that never appears as the first element of a pair has no prerequisites and can be taken immediately.

HAPPY CASE
Input: num_courses = 2, prerequisites = [[1, 0]]
Output: True
Explanation: Take course 0 first, then course 1. Every course can be finished.

EDGE CASE
Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False
Explanation: Course 1 requires course 0 and course 0 requires course 1, forming a cycle. Neither can ever be started.

Input: num_courses = 3, prerequisites = []
Output: True
Explanation: With no prerequisites, every course can be taken in any order.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Dependency Problems, we can consider the following approaches:

Topological Sort (Kahn's Algorithm / BFS): Repeatedly "take" courses with no remaining prerequisites. If we can take all of them, the graph has no cycle.
DFS Cycle Detection: Traverse the graph with DFS, tracking nodes on the current path; revisiting a node on the current path means a cycle exists.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Model the courses as a directed graph where each edge points from a prerequisite to the course that depends on it. Use Kahn's algorithm: count each course's in-degree (number of unfinished prerequisites), start with the courses that have none, and "finish" courses one at a time, unlocking their dependents. If every course gets finished, the prerequisites contain no cycle.

1) Build an adjacency list mapping each prerequisite to the courses that depend on it, and an in-degree count for every course.
2) Add every course with in-degree 0 (no prerequisites) to a queue.
3) While the queue is not empty:
   a) Pop a course and count it as completed.
   b) For each course that depends on it, decrement that course's in-degree.
   c) If a dependent course's in-degree drops to 0, add it to the queue.
4) Return True if the number of completed courses equals num_courses, otherwise False.

⚠️ Common Mistakes

Building the edges backwards: [a, b] means b must come first, so the edge goes from b to a.
Forgetting to seed the queue with all zero in-degree courses, not just course 0.
Returning True as soon as the queue empties instead of checking that every course was completed — leftover courses mean a cycle.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def can_finish(num_courses, prerequisites):
    # Build the adjacency list and in-degree count
    graph = {course: [] for course in range(num_courses)}
    in_degree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)   # prereq -> course
        in_degree[course] += 1

    # Start with every course that has no prerequisites
    queue = deque(course for course in range(num_courses) if in_degree[course] == 0)

    completed = 0
    while queue:
        course = queue.popleft()
        completed += 1
        # "Finish" this course: unlock the courses that depend on it
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    # If every course was completed, there was no cycle
    return completed == num_courses

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input: num_courses = 2, prerequisites = 1, 0
- in_degree = [0, 1], so the queue starts with course 0.
- Finish course 0; course 1's in-degree drops to 0 and it joins the queue.
- Finish course 1. completed = 2 = num_courses.
- Output: True
Input: num_courses = 2, prerequisites = 1, 0], [0, 1
- in_degree = [1, 1], so the queue starts empty.
- No course can be finished. completed = 0 ≠ num_courses.
- Output: False

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume V is the number of courses (num_courses) and E is the number of prerequisite pairs.

Time Complexity: O(V + E) because each course is enqueued and dequeued at most once, and each prerequisite edge is examined exactly once.
Space Complexity: O(V + E) for the adjacency list, the in-degree array, and the queue.

Uh oh!

Prerequisite Check