Course Schedule (Cycle Detection)

▶

Steps

setup

Initialize graph and in-degree array

Create an adjacency list for all courses and initialize in-degree counts to zero for each course.

💡 Setting up these structures is essential to represent course dependencies and track prerequisites.

Line:

graph = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses

💡 We now have empty adjacency lists and zero in-degree counts for all courses.

setup

Build graph and update in-degree from prerequisites

Add edges from each prerequisite to its dependent course and increment the dependent course's in-degree.

💡 This step encodes the prerequisite relationships into the graph and tracks how many prerequisites each course has.

Line:

for dest, src in prerequisites:
    graph[src].append(dest)
    in_degree[dest] += 1

💡 Course 0 has no prerequisites, course 1 depends on course 0.

setup

Initialize queue with courses having zero in-degree

Add all courses with zero in-degree (no prerequisites) to the queue to start processing.

💡 Courses with zero in-degree can be taken immediately, so they start the topological order.

Line:

queue = deque([i for i in range(numCourses) if in_degree[i] == 0])

💡 Only course 0 has zero in-degree and is enqueued.

traverse

Start processing node from queue

Dequeue course 0 from the queue to process it and increment the count of processed courses.

💡 Processing a course means we consider it taken and update dependent courses accordingly.

Line:

node = queue.popleft()
count += 1

💡 Course 0 is now being processed, removed from the queue and marked as done.

traverse

Process neighbor of current node

For course 0, look at its neighbor course 1 and reduce its in-degree by 1.

💡 Reducing in-degree simulates completing a prerequisite, moving closer to being able to take the dependent course.

Line:

for neighbor in graph[node]:
    in_degree[neighbor] -= 1

💡 Course 1's in-degree decreases from 1 to 0, meaning all prerequisites are now satisfied.

traverse

Check if neighbor's in-degree is zero to enqueue

Since course 1's in-degree is now zero, enqueue it to process next.

💡 Enqueuing courses with zero in-degree ensures they are processed in correct order.

Line:

if in_degree[neighbor] == 0:
    queue.append(neighbor)

💡 Course 1 is now ready to be taken and added to the queue.

traverse

Dequeue next node to process

Dequeue course 1 from the queue and increment the processed count.

💡 Processing course 1 means it can be taken after its prerequisites.

Line:

node = queue.popleft()
count += 1

💡 Course 1 is now being processed and removed from the queue.

traverse

Process neighbors of current node (none)

Course 1 has no neighbors, so no in-degree updates or enqueues occur.

💡 Leaf nodes in the graph do not affect other courses' in-degree.

Line:

for neighbor in graph[node]:
    # no neighbors here

💡 No further courses depend on course 1.

traverse

Mark current node as done

Mark course 1 as done and add it to visited list.

💡 Marking done indicates the course has been fully processed.

Line:

# implicit after processing neighbors

💡 Both courses have been processed successfully.

reconstruct

Check if all courses processed and return result

Compare the count of processed courses to total courses to determine if scheduling is possible.

💡 If all courses are processed, no cycle exists and the schedule is valid.

Line:

return count == numCourses

💡 The algorithm confirms no cycle exists and all courses can be completed.

from typing import List
from collections import deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # STEP 1: Initialize graph and in-degree
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses

    # STEP 2: Build graph and update in-degree
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    # STEP 3: Initialize queue with zero in-degree nodes
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0

    # STEP 4-9: Process nodes in queue
    while queue:
        node = queue.popleft()  # STEP 4 & 7
        count += 1
        for neighbor in graph[node]:  # STEP 5 & 8
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:  # STEP 6
                queue.append(neighbor)

    # STEP 10: Check if all courses processed
    return count == numCourses

📊

Course Schedule (Cycle Detection) - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how Kahn's algorithm uses in-degree and queue to detect cycles without recursion.

Visiting: none

0

1

Visiting: none

0

1

Visiting: none

0

1

Queue / Stack

0

Visiting: 0

0

1

Visiting: 0

Edge: 0 → 1

0

1

Visiting: 0

Edge: 0 → 1

0

1

Queue / Stack

1

Visiting: 1

0

1

Visiting: 1

0

1

Visiting: 1

0

1

Visiting: none

0

1

Key Takeaways

✓ Kahn's algorithm uses in-degree counts and a queue to detect cycles without recursion.

This insight is hard to see from code alone because the queue and in-degree interplay is subtle and dynamic.

✓ Courses with zero in-degree represent nodes ready to be taken, driving the topological order.

Visualizing the queue contents clarifies how the algorithm prioritizes courses.

✓ If all courses are processed, no cycle exists; otherwise, a cycle prevents completion.

The processed count compared to total courses is the key decision point, which is clearer when traced step-by-step.

Practice

1. You are given a 2D grid of 0s and 1s. For each cell containing 1, you need to find the distance to the nearest 0. Which algorithmic approach guarantees the shortest distance for all cells efficiently?

easy

A. Use a multi-source Breadth-First Search (BFS) starting from all 0s simultaneously.

B. Run a Depth-First Search (DFS) from each 1 to find the nearest 0.

C. Apply a greedy approach updating distances by scanning rows and columns once.

D. Use a brute force approach checking every cell independently for nearest 0.

Solution

1. Step 1: Understand the problem constraints

   We need shortest distances from each 1 to the nearest 0 in a grid, which is a shortest path problem on an unweighted graph.

2. Step 2: Identify the correct algorithm

   Multi-source BFS starting from all 0s simultaneously guarantees shortest distances because BFS explores neighbors in increasing order of distance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS ensures shortest path in O(m*n) time [OK]

Hint: Shortest path in grid with multiple sources -> multi-source BFS [OK]

Common Mistakes:

• Using DFS which does not guarantee shortest path
• Greedy scanning misses some paths
• Brute force is too slow

2. You are given a town with n people labeled from 1 to n. Some people trust others, represented as pairs [a, b] meaning person a trusts person b. The town judge is defined as someone who trusts nobody but is trusted by everyone else. Which approach guarantees finding the town judge efficiently?

easy

A. Use a single array to track trust scores by incrementing for trusted and decrementing for trusting, then find the person with score n-1.

B. Use a brute force approach checking each person by scanning the entire trust list twice.

C. Use dynamic programming to build a trust matrix and find the person with the highest trust count.

D. Use a greedy approach to pick the person trusted by the most and verify if they trust nobody.

Solution

1. Step 1: Understand the problem constraints

   The town judge trusts nobody and is trusted by everyone else, so their trust score should be exactly n-1.

2. Step 2: Use a single trust score array

   Increment the score for each person trusted and decrement for each person who trusts someone else. The judge will have a score of n-1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with trust score array finds judge efficiently [OK]

Hint: Trust score array captures trust relationships efficiently [OK]

Common Mistakes:

• Assuming greedy max trusted person is always judge
• Using DP unnecessarily
• Brute force is too slow for large inputs

3. Consider the following code snippet for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        nonlocal count
        if visited[room]:
            return
        visited[room] = true
        count += 1
        if count == n:
            return
        for key in rooms[room]:
            dfs(key)
    dfs(0)
    return count == n

rooms = [[1], [2], [3], []]
print(canVisitAllRooms(rooms))

What is the value of count after the DFS call completes?

easy

A. 3

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace DFS calls starting from room 0

   Visit room 0 (count=1), then room 1 (count=2), then room 2 (count=3), then room 3 (count=4).

2. Step 2: Confirm all rooms visited

   Since count equals total rooms (4), DFS stops early and returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All rooms reachable, count matches number of rooms [OK]

Hint: Count increments once per unique room visited [OK]

Common Mistakes:

• Off-by-one error counting rooms
• Assuming count stops at 3 instead of 4
• Confusing count with length of visited list

4. You are given a matrix representing heights of cells on a grid. Water can flow from a cell to its neighboring cells if the neighbor's height is less than or equal to the current cell's height. Find all cells from which water can flow to both the top-left and bottom-right edges of the grid. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use dynamic programming to store maximum reachable heights and combine results.

B. Run DFS from every cell to check if it can reach both edges independently.

C. Run BFS or DFS starting from the edges inward, marking reachable cells for each edge, then find their intersection.

D. Apply a greedy approach by always moving to the neighbor with the highest height.

Solution

1. Step 1: Understand flow direction

   Water flows from higher or equal height to lower or equal height neighbors, so starting from edges inward ensures we only visit reachable cells.

2. Step 2: Reverse BFS/DFS from edges

   By running BFS/DFS from the edges inward, we mark all cells that can flow to each ocean, then intersect these sets to find cells that can flow to both.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starting from edges avoids repeated DFS from every cell [OK]

Hint: Reverse BFS/DFS from edges is optimal [OK]

Common Mistakes:

• Thinking BFS/DFS must start from each cell
• Using greedy approach fails on plateaus

5. Suppose the graph edges can be reused multiple times (i.e., the graph can have parallel edges and cycles). Which modification to the BFS-based valid_tree algorithm correctly determines if the graph is still a valid tree under these relaxed constraints?

hard

A. Use Union-Find data structure to detect cycles and ensure connectivity despite parallel edges.

B. Remove the edge count check and rely solely on BFS cycle detection.

C. Modify BFS to ignore revisiting any node regardless of parent to handle parallel edges.

D. Count edges and nodes, and if edges >= n, return false immediately.

Solution

1. Step 1: Understand problem change

   Allowing parallel edges and cycles breaks the simple edge count == n-1 assumption.

2. Step 2: Identify robust approach

   Union-Find efficiently detects cycles and connectivity even with parallel edges and multiple components.

3. Step 3: Why other options fail

   Removing edge count check loses pruning; ignoring revisits breaks cycle detection; counting edges >= n is insufficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Union-Find handles complex graphs with cycles and parallel edges [OK]

Hint: Union-Find handles cycle detection with parallel edges [OK]

Common Mistakes:

• Relying on edge count only
• Ignoring revisits incorrectly
• Simple BFS fails with parallel edges