Course Schedule (Cycle Detection)

📋

Course Schedule (Cycle Detection)

Edge cases:

</>

IDE

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:public boolean canFinish(int numCourses, int[][] prerequisites)bool canFinish(int numCourses, vector<vector<int>>& prerequisites)function canFinish(numCourses, prerequisites)

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // Write your solution here
    return false;
}

function canFinish(numCourses, prerequisites) {
    // Write your solution here
    return false;
}

Common Bugs to Avoid

Wrong: falseCycle detection logic misses that no cycle exists and returns false incorrectly.✅ Ensure recursion stack or node states are tracked correctly; return true if no cycles found.

Wrong: trueCycle detection misses cycles due to not tracking recursion stack or node states properly.✅ Implement three-state coloring or recursion stack to detect back edges indicating cycles.

Wrong: trueSelf-dependency cycles not detected, returning true incorrectly.✅ Check for self-loops explicitly or rely on cycle detection to catch them.

Wrong: falseEmpty input or no prerequisites treated as false.✅ Return true immediately if numCourses is zero or no edges exist.

Wrong: nullAlgorithm is too slow and times out on large inputs.✅ Use O(V+E) DFS or BFS with adjacency list and visited states to avoid TLE.

✓

Test Cases

Focus on handling edge cases like empty graphs and self-loops.

Test your code against tricky cycles and branching dependencies.

Ensure your solution runs efficiently on large inputs using O(V+E) algorithms.

t1_01basic

Input{"numCourses":2,"prerequisites":[[1,0]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

You can take course 0 first, then course 1, so no cycle exists.

💡 Think about representing courses and prerequisites as a directed graph.

💡 Use DFS or BFS to detect cycles in the graph.

💡 If no cycle is detected, return true; otherwise, false.

Why it failed: Returned false incorrectly - likely cycle detection logic is flawed or missing base case. Fix by properly tracking recursion stack or node states.

✓ Correctly identified no cycle; basic cycle detection logic works.

t1_02basic

Input{"numCourses":3,"prerequisites":[[0,1],[1,2]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Courses can be taken in order 2 -> 1 -> 0 with no cycles.

💡 Check if the graph has any back edges indicating cycles.

💡 Use a three-state coloring method (unvisited, visiting, visited) to detect cycles.

💡 Return true if no back edges found during DFS traversal.

Why it failed: Incorrectly returned false - likely cycle detection does not handle linear chains correctly. Fix by ensuring DFS visits all nodes and tracks recursion stack properly.

✓ Correctly handled linear chain of prerequisites without cycles.

t2_01edge

Input{"numCourses":0,"prerequisites":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

No courses means trivially possible to finish all (none).

💡 Consider the base case when there are no courses.

💡 An empty graph has no cycles by definition.

💡 Return true immediately if numCourses is zero.

Why it failed: Returned false on empty input - must handle zero courses as a base case returning true.

✓ Correctly handled empty input as trivially finishable.

t2_02edge

Input{"numCourses":1,"prerequisites":[[0,0]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single course with self-dependency forms a cycle, so cannot finish.

💡 Check for self-loops in the graph which form immediate cycles.

💡 Cycle detection must catch edges from a node to itself.

💡 Return false if any course depends on itself.

Why it failed: Returned true despite self-dependency cycle - fix by detecting self-loops explicitly or via cycle detection.

✓ Correctly detected self-dependency cycle and returned false.

t2_03edge

Input{"numCourses":1000,"prerequisites":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Many courses but no prerequisites means no cycles, so all can be finished.

💡 Large graphs with no edges are acyclic.

💡 Cycle detection should handle disconnected graphs correctly.

💡 Return true if no edges exist regardless of number of courses.

Why it failed: Returned false on large graph with no edges - fix by ensuring cycle detection handles empty adjacency lists correctly.

✓ Correctly handled large graph with no edges as acyclic.

t2_04edge

Input{"numCourses":2,"prerequisites":[[0,1],[1,0]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Two courses with mutual dependency form a cycle, so cannot finish.

💡 Detect cycles involving two nodes pointing to each other.

💡 DFS recursion stack or coloring must catch these cycles.

💡 Return false if any cycle detected, even between two nodes.

Why it failed: Returned true despite mutual dependency cycle - fix by properly tracking recursion stack or node states.

✓ Correctly detected mutual dependency cycle and returned false.

t3_01corner

Input{"numCourses":4,"prerequisites":[[1,0],[2,1],[3,2],[1,3]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Cycle exists: 1 -> 3 -> 2 -> 1, so cannot finish all courses.

💡 Detect cycles that form in longer chains, not just immediate neighbors.

💡 Use DFS with recursion stack or three-state coloring to catch cycles.

💡 Ensure cycle detection tracks all nodes in recursion stack to catch indirect cycles.

Why it failed: Returned true despite cycle in chain - fix by properly tracking recursion stack or node states during DFS.

✓ Correctly detected cycle in chain and returned false.

t3_02corner

Input{"numCourses":3,"prerequisites":[[0,1],[1,2],[2,0]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Cycle exists among all courses: 0 -> 1 -> 2 -> 0.

💡 Check for cycles involving all nodes in the graph.

💡 Topological sort fails if cycle exists; use it to detect cycles.

💡 Return false if topological sort cannot include all nodes.

Why it failed: Returned true despite cycle involving all nodes - fix by verifying topological sort includes all nodes or cycle detection is complete.

✓ Correctly detected full cycle and returned false.

t3_03corner

Input{"numCourses":5,"prerequisites":[[1,0],[2,0],[3,1],[3,2],[4,3]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

No cycles; dependencies form a DAG allowing all courses to be finished.

💡 Verify that multiple branches without cycles are handled correctly.

💡 DFS or BFS should traverse all nodes and confirm no back edges.

💡 Return true if all nodes can be topologically ordered.

Why it failed: Returned false incorrectly - likely cycle detection misfires on branching DAGs. Fix by ensuring no false positives in cycle detection.

✓ Correctly handled branching DAG with no cycles.

t4_01performance

Input{"numCourses":100,"prerequisites":[[1,0],[2,1],[3,2],[4,3],[5,4],[6,5],[7,6],[8,7],[9,8],[10,9],[11,10],[12,11],[13,12],[14,13],[15,14],[16,15],[17,16],[18,17],[19,18],[20,19],[21,20],[22,21],[23,22],[24,23],[25,24],[26,25],[27,26],[28,27],[29,28],[30,29],[31,30],[32,31],[33,32],[34,33],[35,34],[36,35],[37,36],[38,37],[39,38],[40,39],[41,40],[42,41],[43,42],[44,43],[45,44],[46,45],[47,46],[48,47],[49,48],[50,49],[51,50],[52,51],[53,52],[54,53],[55,54],[56,55],[57,56],[58,57],[59,58],[60,59],[61,60],[62,61],[63,62],[64,63],[65,64],[66,65],[67,66],[68,67],[69,68],[70,69],[71,70],[72,71],[73,72],[74,73],[75,74],[76,75],[77,76],[78,77],[79,78],[80,79],[81,80],[82,81],[83,82],[84,83],[85,84],[86,85],[87,86],[88,87],[89,88],[90,89],[91,90],[92,91],[93,92],[94,93],[95,94],[96,95],[97,96],[98,97],[99,98]]}

Expectednull

⏱ Performance - must finish in 2000ms

Chain of 100 courses with linear dependencies; O(V+E) = O(200) must complete within 2 seconds.

💡 Use DFS or BFS with adjacency list for O(V+E) complexity.

💡 Avoid repeated work by marking visited nodes.

💡 Topological sort or DFS coloring are efficient for large inputs.

Why it failed: TLE due to exponential or inefficient cycle detection (e.g., repeated DFS without memoization). Fix by using O(V+E) algorithms with proper visited tracking.

✓ Algorithm runs in O(V+E) time confirming efficient cycle detection.

Practice

1. You are given a list of edges representing an undirected graph with n nodes labeled from 0 to n-1. You need to determine if the graph forms a valid tree. Which algorithmic approach guarantees an optimal solution to check both connectivity and absence of cycles efficiently?

easy

A. Use a greedy algorithm that adds edges one by one and checks if the graph remains connected.

B. Apply dynamic programming to count the number of ways to reach each node and detect cycles.

C. Sort edges and use binary search to detect cycles and connectivity.

D. Perform a BFS or DFS traversal to detect cycles and verify that all nodes are connected.

Solution

1. Step 1: Understand problem requirements

   The problem requires checking if the graph is connected and contains no cycles, which defines a tree.

2. Step 2: Identify suitable algorithm

   BFS or DFS traversal can detect cycles by tracking visited nodes and parent relationships, and also verify connectivity by ensuring all nodes are visited.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS/DFS simultaneously checks connectivity and cycles efficiently [OK]

Hint: Trees have n-1 edges and no cycles [OK]

Common Mistakes:

• Assuming greedy edge addition ensures connectivity
• Using DP which is unrelated here

2. Consider the following buggy code snippet for the 01 Matrix problem. Which line contains the subtle bug that can cause incorrect distances or runtime errors?

medium

A. Line initializing dist with float('inf')

B. Line setting dist[i][j] = 0 when mat[i][j] == 0

C. Line with 'if i >= 0:' condition

D. Line with 'if j < n - 1:' condition in backward pass

Solution

1. Step 1: Analyze the condition 'if i >= 0:'

   This condition is always true for i in range(m), so dist[i-1][j] access is unsafe when i=0 (index -1).

2. Step 2: Identify the bug

   Accessing dist[-1][j] causes incorrect behavior or runtime error; correct condition should be 'if i > 0:'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary check off-by-one leads to invalid index [OK]

Hint: Check boundary conditions carefully to avoid invalid indices [OK]

Common Mistakes:

• Off-by-one in boundary checks
• Incorrect initialization
• Misplaced conditions

3. Examine the following buggy code for the Keys and Rooms problem:

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

What is the bug in this code?

medium

A. Visited marking happens after recursive calls, causing repeated visits

B. Count is incremented before marking visited, causing off-by-one errors

C. Visited array is initialized incorrectly with zeros instead of false

D. DFS is called on room 0 instead of all rooms

Solution

1. Step 1: Analyze visited marking position

   Visited is marked after recursive calls, so the same room can be visited multiple times during recursion.

2. Step 2: Identify consequence of bug

   This causes repeated visits and potentially infinite recursion or incorrect count.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited must be marked before recursion to avoid revisits [OK]

Hint: Mark visited before recursion to prevent repeated visits [OK]

Common Mistakes:

• Marking visited after recursion leads to infinite loops
• Incrementing count before visited marking
• Incorrect initialization of visited array

4. What is the time complexity of the optimal BFS approach for the Pacific Atlantic Water Flow problem on an m x n grid, and why?

medium

A. O(m * n) because each cell is enqueued and processed at most once per ocean.

B. O(m * n * log(m * n)) due to priority queue operations in BFS.

C. O(m^2 * n^2) because BFS is run from every cell.

D. O(m + n) because BFS only processes border cells.

Solution

1. Step 1: Analyze BFS visits

   Each BFS starts from border cells and visits each cell at most once per ocean, so total visits ≤ 2 * m * n.

2. Step 2: Confirm no repeated work

   Visited arrays prevent revisiting cells, so BFS complexity is linear in number of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each cell processed once per ocean -> O(m*n) [OK]

Hint: BFS visits each cell once per ocean [OK]

Common Mistakes:

• Confusing with brute force DFS from every cell
• Assuming BFS uses priority queue

5. Suppose the problem is modified so that islands can be connected diagonally as well (8-direction connectivity). Which of the following changes to the DFS approach correctly counts islands under this new rule?

hard

A. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to the DFS calls in addition to the four cardinal directions.

B. Keep the DFS calls unchanged but count diagonally adjacent '1's separately after DFS completes.

C. Use BFS instead of DFS without changing neighbor directions, as BFS handles diagonal connectivity automatically.

D. Modify the grid to mark diagonal neighbors as '1' before running the original DFS.

Solution

1. Step 1: Understand the new connectivity rule

   Islands now connect horizontally, vertically, and diagonally, so DFS must explore all 8 neighbors.

2. Step 2: Modify DFS to include diagonal neighbors

   Add recursive DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), and (r-1,c-1) along with the original four directions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only adding diagonal neighbors to DFS ensures correct island counting with 8-direction connectivity [OK]

Hint: Add diagonal neighbors to DFS for 8-direction connectivity [OK]

Common Mistakes:

• Assuming BFS handles diagonals without code change
• Counting diagonals separately after DFS