Course Schedule (Cycle Detection)

🎯

Course Schedule (Cycle Detection)

mediumGRAPHAmazonFacebookGoogle

Imagine you are planning your university courses, but some courses require others as prerequisites. You want to know if it's possible to finish all courses without getting stuck in a circular dependency.

💡 This problem is about detecting cycles in a directed graph, which is a fundamental concept in graph theory. Beginners often struggle because cycles in directed graphs are less intuitive than in undirected graphs, and naive approaches can be inefficient or incorrect.

📋

Problem Statement

Given the number of courses n labeled from 0 to n-1 and a list of prerequisite pairs where each pair [a, b] indicates that course a depends on course b, determine if it is possible to finish all courses. Return true if you can finish all courses, otherwise false.

1 ≤ n ≤ 10^50 ≤ number of prerequisite pairs ≤ 10^5No duplicate prerequisite pairs

💡

Example

Input"n = 2, prerequisites = [[1,0]]"

Outputtrue

You can take course 0 first, then course 1.

Input"n = 2, prerequisites = [[1,0],[0,1]]"

Outputfalse

There is a cycle between course 0 and 1, so you cannot finish.

• No prerequisites → always true
• Single course with a self-dependency → false
• Large number of courses but no edges → true
• Chain of dependencies with a cycle at the end → false

⚠️

Common Mistakes

Using only a visited set without recursion stack or coloring

Fails to detect cycles correctly, returns true even if cycle exists

✅ Use a recursion stack or three-state coloring to track nodes in current DFS path

Not building the graph correctly (reversing edges)

Incorrect cycle detection or wrong results

✅ Ensure edges are from prerequisite to dependent course (src -> dest)

Modifying the graph or in-degree array during iteration incorrectly

Runtime errors or infinite loops

✅ Update in-degree carefully and only after dequeuing nodes

Ignoring self-loops as cycles

Returns true incorrectly when a course depends on itself

✅ Detect self-loops as cycles during DFS or in-degree checks

Using recursion without handling large input stack limits

Stack overflow or runtime errors on large graphs

✅ Use iterative BFS topological sort or increase recursion limits carefully

🧠

Brute Force (DFS with Recursion and Cycle Detection Using Visited Set)

💡 This approach introduces the fundamental idea of cycle detection using DFS and recursion. It is simple to understand but inefficient for large inputs due to repeated work and lack of memoization.

Intuition

Perform a DFS from each course to check if a cycle exists by tracking the recursion stack. If a node is revisited in the current path, a cycle is detected.

Algorithm

1. Build an adjacency list from the prerequisites.
2. For each course, if not visited, perform DFS.
3. During DFS, mark nodes in the recursion stack.
4. If a node is found in the recursion stack, return false (cycle detected).
5. If DFS completes without cycles, return true.

💡 The challenge is to track nodes currently in the recursion path separately from nodes already fully explored to detect cycles correctly.

</>

Code

from typing import List

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    for dest, src in prerequisites:
        graph[src].append(dest)

    visited = set()
    recStack = set()

    def dfs(node):
        if node in recStack:
            return False
        if node in visited:
            return True

        recStack.add(node)
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        recStack.remove(node)
        visited.add(node)
        return True

    for course in range(numCourses):
        if course not in visited:
            if not dfs(course):
                return False
    return True

# Driver code
if __name__ == '__main__':
    print(canFinish(2, [[1,0]]))  # True
    print(canFinish(2, [[1,0],[0,1]]))  # False

Line Notes

graph = [[] for _ in range(numCourses)]Initialize adjacency list for all courses

for dest, src in prerequisites:Build edges from source to destination

visited = set()Tracks nodes fully processed to avoid reprocessing

recStack = set()Tracks nodes in current DFS path to detect cycles

if node in recStack:Cycle detected if node revisited in current path

if node in visited:Skip nodes already processed without cycles

recStack.add(node)Mark node as part of current recursion stack

for neighbor in graph[node]:Explore all dependent courses

recStack.remove(node)Remove node from recursion stack after processing

visited.add(node)Mark node as fully processed

for course in range(numCourses):Check all courses for cycles

if not dfs(course):If cycle found, return False immediately

import java.util.*;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
        }

        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();

        for (int course = 0; course < numCourses; course++) {
            if (!visited.contains(course)) {
                if (!dfs(course, graph, visited, recStack)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int node, List<List<Integer>> graph, Set<Integer> visited, Set<Integer> recStack) {
        if (recStack.contains(node)) {
            return false;
        }
        if (visited.contains(node)) {
            return true;
        }

        recStack.add(node);
        for (int neighbor : graph.get(node)) {
            if (!dfs(neighbor, graph, visited, recStack)) {
                return false;
            }
        }
        recStack.remove(node);
        visited.add(node);
        return true;
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canFinish(2, new int[][]{{1,0}})); // true
        System.out.println(sol.canFinish(2, new int[][]{{1,0},{0,1}})); // false
    }
}

Line Notes

List<List<Integer>> graph = new ArrayList<>();Initialize adjacency list for courses

for (int[] pair : prerequisites)Build graph edges from prerequisites

Set<Integer> visited = new HashSet<>();Tracks fully processed nodes

Set<Integer> recStack = new HashSet<>();Tracks nodes in current DFS path

if (recStack.contains(node))Detect cycle if node revisited in recursion stack

if (visited.contains(node))Skip nodes already processed

recStack.add(node);Add node to recursion stack before DFS

for (int neighbor : graph.get(node))Traverse neighbors recursively

recStack.remove(node);Remove node after DFS completes

visited.add(node);Mark node as fully processed

for (int course = 0; course < numCourses; course++)Check all courses for cycles

if (!dfs(course, graph, visited, recStack))Return false if cycle detected

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }

        unordered_set<int> visited;
        unordered_set<int> recStack;

        for (int course = 0; course < numCourses; ++course) {
            if (visited.find(course) == visited.end()) {
                if (!dfs(course, graph, visited, recStack)) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    bool dfs(int node, vector<vector<int>>& graph, unordered_set<int>& visited, unordered_set<int>& recStack) {
        if (recStack.count(node)) return false;
        if (visited.count(node)) return true;

        recStack.insert(node);
        for (int neighbor : graph[node]) {
            if (!dfs(neighbor, graph, visited, recStack)) {
                return false;
            }
        }
        recStack.erase(node);
        visited.insert(node);
        return true;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> prereq1 = {{1,0}};
    cout << boolalpha << sol.canFinish(2, prereq1) << endl; // true
    vector<vector<int>> prereq2 = {{1,0},{0,1}};
    cout << boolalpha << sol.canFinish(2, prereq2) << endl; // false
    return 0;
}

Line Notes

vector<vector<int>> graph(numCourses);Create adjacency list for graph

for (auto& p : prerequisites)Build edges from prerequisites

unordered_set<int> visited;Stores nodes fully processed

unordered_set<int> recStack;Stores nodes in current DFS path

if (recStack.count(node)) return false;Cycle detected if node revisited in recursion stack

if (visited.count(node)) return true;Skip nodes already processed

recStack.insert(node);Add node to recursion stack before DFS

for (int neighbor : graph[node])Traverse neighbors recursively

recStack.erase(node);Remove node after DFS completes

visited.insert(node);Mark node as fully processed

for (int course = 0; course < numCourses; ++course)Check all courses for cycles

if (!dfs(course, graph, visited, recStack))Return false if cycle detected

function canFinish(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    for (const [dest, src] of prerequisites) {
        graph[src].push(dest);
    }

    const visited = new Set();
    const recStack = new Set();

    function dfs(node) {
        if (recStack.has(node)) return false;
        if (visited.has(node)) return true;

        recStack.add(node);
        for (const neighbor of graph[node]) {
            if (!dfs(neighbor)) return false;
        }
        recStack.delete(node);
        visited.add(node);
        return true;
    }

    for (let course = 0; course < numCourses; course++) {
        if (!visited.has(course)) {
            if (!dfs(course)) return false;
        }
    }
    return true;
}

// Test cases
console.log(canFinish(2, [[1,0]])); // true
console.log(canFinish(2, [[1,0],[0,1]])); // false

Line Notes

const graph = Array.from({length: numCourses}, () => []);Initialize adjacency list

for (const [dest, src] of prerequisites)Build graph edges

const visited = new Set();Tracks fully processed nodes

const recStack = new Set();Tracks nodes in current DFS path

if (recStack.has(node)) return false;Detect cycle if node revisited in recursion stack

if (visited.has(node)) return true;Skip nodes already processed

recStack.add(node);Add node to recursion stack before DFS

for (const neighbor of graph[node])Traverse neighbors recursively

recStack.delete(node);Remove node after DFS completes

visited.add(node);Mark node as fully processed

for (let course = 0; course < numCourses; course++)Check all courses for cycles

if (!dfs(course)) return false;Return false if cycle detected

⏱

Complexity

TimeO(V + E)

SpaceO(V + E)

Each node and edge is visited once in DFS. The recursion stack and visited sets use O(V) space.

💡 For 100,000 courses and edges, this means roughly 200,000 operations, which is feasible but can be slow without optimization.

Interview Verdict: Accepted but can be inefficient for large inputs due to repeated DFS calls.

This approach works but can be improved by avoiding repeated DFS on nodes already confirmed acyclic.

🧠

DFS with Coloring (Three States) to Detect Cycles

💡 This approach improves cycle detection clarity and efficiency by using three states (unvisited, visiting, visited) instead of two sets, reducing overhead and making the logic explicit.

Intuition

Mark nodes as unvisited (0), visiting (1), or visited (2). If during DFS you reach a node marked visiting, a cycle exists.

Algorithm

1. Build adjacency list from prerequisites.
2. Initialize all nodes as unvisited (0).
3. For each node, if unvisited, perform DFS.
4. Mark node as visiting (1) when DFS starts.
5. If a neighbor is visiting, cycle detected.
6. After DFS, mark node as visited (2).
7. Return false if cycle found, else true.

💡 The three states help differentiate nodes currently in the recursion stack from those fully processed, simplifying cycle detection.

</>

Code

from typing import List

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    for dest, src in prerequisites:
        graph[src].append(dest)

    state = [0] * numCourses  # 0=unvisited,1=visiting,2=visited

    def dfs(node):
        if state[node] == 1:
            return False
        if state[node] == 2:
            return True

        state[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        state[node] = 2
        return True

    for course in range(numCourses):
        if state[course] == 0:
            if not dfs(course):
                return False
    return True

# Driver code
if __name__ == '__main__':
    print(canFinish(2, [[1,0]]))  # True
    print(canFinish(2, [[1,0],[0,1]]))  # False

Line Notes

state = [0] * numCoursesInitialize all nodes as unvisited

if state[node] == 1:Cycle detected if node is currently being visited

if state[node] == 2:Skip nodes already fully visited

state[node] = 1Mark node as visiting when DFS starts

for neighbor in graph[node]:Traverse neighbors recursively

state[node] = 2Mark node as visited after DFS completes

for course in range(numCourses):Check all courses for cycles

if not dfs(course):Return false if cycle detected

import java.util.*;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
        }

        int[] state = new int[numCourses]; // 0=unvisited,1=visiting,2=visited

        for (int course = 0; course < numCourses; course++) {
            if (state[course] == 0) {
                if (!dfs(course, graph, state)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int node, List<List<Integer>> graph, int[] state) {
        if (state[node] == 1) return false;
        if (state[node] == 2) return true;

        state[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (!dfs(neighbor, graph, state)) {
                return false;
            }
        }
        state[node] = 2;
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canFinish(2, new int[][]{{1,0}})); // true
        System.out.println(sol.canFinish(2, new int[][]{{1,0},{0,1}})); // false
    }
}

Line Notes

int[] state = new int[numCourses];Initialize all nodes as unvisited

if (state[node] == 1) return false;Cycle detected if node is currently visiting

if (state[node] == 2) return true;Skip nodes already visited

state[node] = 1;Mark node as visiting

for (int neighbor : graph.get(node))Traverse neighbors recursively

state[node] = 2;Mark node as visited after DFS

for (int course = 0; course < numCourses; course++)Check all courses for cycles

if (!dfs(course, graph, state))Return false if cycle detected

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }

        vector<int> state(numCourses, 0); // 0=unvisited,1=visiting,2=visited

        for (int course = 0; course < numCourses; ++course) {
            if (state[course] == 0) {
                if (!dfs(course, graph, state)) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    bool dfs(int node, vector<vector<int>>& graph, vector<int>& state) {
        if (state[node] == 1) return false;
        if (state[node] == 2) return true;

        state[node] = 1;
        for (int neighbor : graph[node]) {
            if (!dfs(neighbor, graph, state)) {
                return false;
            }
        }
        state[node] = 2;
        return true;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> prereq1 = {{1,0}};
    cout << boolalpha << sol.canFinish(2, prereq1) << endl; // true
    vector<vector<int>> prereq2 = {{1,0},{0,1}};
    cout << boolalpha << sol.canFinish(2, prereq2) << endl; // false
    return 0;
}

Line Notes

vector<int> state(numCourses, 0);Initialize all nodes as unvisited

if (state[node] == 1) return false;Cycle detected if node is visiting

if (state[node] == 2) return true;Skip nodes already visited

state[node] = 1;Mark node as visiting

for (int neighbor : graph[node])Traverse neighbors recursively

state[node] = 2;Mark node as visited after DFS

for (int course = 0; course < numCourses; ++course)Check all courses for cycles

if (!dfs(course, graph, state))Return false if cycle detected

function canFinish(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    for (const [dest, src] of prerequisites) {
        graph[src].push(dest);
    }

    const state = new Array(numCourses).fill(0); // 0=unvisited,1=visiting,2=visited

    function dfs(node) {
        if (state[node] === 1) return false;
        if (state[node] === 2) return true;

        state[node] = 1;
        for (const neighbor of graph[node]) {
            if (!dfs(neighbor)) return false;
        }
        state[node] = 2;
        return true;
    }

    for (let course = 0; course < numCourses; course++) {
        if (state[course] === 0) {
            if (!dfs(course)) return false;
        }
    }
    return true;
}

// Test cases
console.log(canFinish(2, [[1,0]])); // true
console.log(canFinish(2, [[1,0],[0,1]])); // false

Line Notes

const state = new Array(numCourses).fill(0);Initialize all nodes as unvisited

if (state[node] === 1) return false;Cycle detected if node is visiting

if (state[node] === 2) return true;Skip nodes already visited

state[node] = 1;Mark node as visiting

for (const neighbor of graph[node])Traverse neighbors recursively

state[node] = 2;Mark node as visited after DFS

for (let course = 0; course < numCourses; course++)Check all courses for cycles

if (!dfs(course)) return false;Return false if cycle detected

⏱

Complexity

TimeO(V + E)

SpaceO(V + E)

Each node and edge is visited once. The state array uses O(V) space.

💡 This approach is more efficient and clearer than the brute force recursion stack method, making it better for large inputs.

Interview Verdict: Accepted and preferred over brute force due to clarity and efficiency.

This is the standard DFS cycle detection approach in interviews for directed graphs.

🧠

Topological Sort Using Kahn's Algorithm (BFS)

💡 This approach uses BFS and in-degree counting to detect cycles by attempting to build a topological order. If all nodes can be processed, no cycle exists.

Intuition

Courses with no prerequisites can be taken first. Remove them and update dependent courses. If some courses remain with prerequisites, a cycle exists.

Algorithm

1. Build adjacency list and compute in-degree for each node.
2. Initialize a queue with nodes having in-degree zero.
3. While queue not empty, dequeue node and reduce in-degree of neighbors.
4. If neighbor's in-degree becomes zero, enqueue it.
5. Count processed nodes; if count equals total courses, return true.
6. Otherwise, return false indicating a cycle.

💡 This approach avoids recursion and uses a queue to process nodes in order, making cycle detection intuitive and efficient.

</>

Code

from typing import List
from collections import deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

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

    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return count == numCourses

# Driver code
if __name__ == '__main__':
    print(canFinish(2, [[1,0]]))  # True
    print(canFinish(2, [[1,0],[0,1]]))  # False

Line Notes

in_degree = [0] * numCoursesInitialize in-degree count for each course

graph[src].append(dest)Build adjacency list

in_degree[dest] += 1Increment in-degree for dependent course

queue = deque([i for i in range(numCourses) if in_degree[i] == 0])Start with courses having no prerequisites

while queue:Process courses in BFS order

count += 1Count courses that can be taken

in_degree[neighbor] -= 1Remove dependency as course is taken

if in_degree[neighbor] == 0:Enqueue courses that become available

import java.util.*;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses];
        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
            inDegree[pair[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) queue.offer(neighbor);
            }
        }

        return count == numCourses;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canFinish(2, new int[][]{{1,0}})); // true
        System.out.println(sol.canFinish(2, new int[][]{{1,0},{0,1}})); // false
    }
}

Line Notes

int[] inDegree = new int[numCourses];Initialize in-degree array

graph.get(pair[1]).add(pair[0]);Build adjacency list

inDegree[pair[0]]++;Increment in-degree for dependent course

if (inDegree[i] == 0) queue.offer(i);Add courses with no prerequisites to queue

while (!queue.isEmpty())Process courses in BFS order

count++;Count courses that can be taken

inDegree[neighbor]--;Remove dependency as course is taken

if (inDegree[neighbor] == 0) queue.offer(neighbor);Enqueue newly available courses

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
            inDegree[p[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) q.push(i);
        }

        int count = 0;
        while (!q.empty()) {
            int node = q.front(); q.pop();
            count++;
            for (int neighbor : graph[node]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) q.push(neighbor);
            }
        }

        return count == numCourses;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> prereq1 = {{1,0}};
    cout << boolalpha << sol.canFinish(2, prereq1) << endl; // true
    vector<vector<int>> prereq2 = {{1,0},{0,1}};
    cout << boolalpha << sol.canFinish(2, prereq2) << endl; // false
    return 0;
}

Line Notes

vector<int> inDegree(numCourses, 0);Initialize in-degree vector

graph[p[1]].push_back(p[0]);Build adjacency list

inDegree[p[0]]++;Increment in-degree for dependent course

if (inDegree[i] == 0) q.push(i);Add courses with no prerequisites to queue

while (!q.empty())Process courses in BFS order

count++;Count courses that can be taken

inDegree[neighbor]--;Remove dependency as course is taken

if (inDegree[neighbor] == 0) q.push(neighbor);Enqueue newly available courses

function canFinish(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    const inDegree = new Array(numCourses).fill(0);
    for (const [dest, src] of prerequisites) {
        graph[src].push(dest);
        inDegree[dest]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }

    let count = 0;
    while (queue.length > 0) {
        const node = queue.shift();
        count++;
        for (const neighbor of graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) queue.push(neighbor);
        }
    }

    return count === numCourses;
}

// Test cases
console.log(canFinish(2, [[1,0]])); // true
console.log(canFinish(2, [[1,0],[0,1]])); // false

Line Notes

const inDegree = new Array(numCourses).fill(0);Initialize in-degree array

graph[src].push(dest);Build adjacency list

inDegree[dest]++;Increment in-degree for dependent course

if (inDegree[i] === 0) queue.push(i);Add courses with no prerequisites to queue

while (queue.length > 0)Process courses in BFS order

count++;Count courses that can be taken

inDegree[neighbor]--;Remove dependency as course is taken

if (inDegree[neighbor] === 0) queue.push(neighbor);Enqueue newly available courses

⏱

Complexity

TimeO(V + E)

SpaceO(V + E)

Each node and edge is processed once. The queue and in-degree array use O(V) space.

💡 This approach is often faster in practice and avoids recursion stack issues, making it a robust interview solution.

Interview Verdict: Accepted and optimal for large inputs; preferred when BFS is allowed.

This approach is a classic topological sort and is often favored for cycle detection in directed graphs.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, approach 2 (DFS with coloring) or approach 3 (BFS topological sort) are best to code. Approach 1 is useful to explain the basics but not to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with recursion stack)	O(V + E)	O(V + E)	Yes (deep recursion)	No	Mention only - never code
2. DFS with Coloring (Three States)	O(V + E)	O(V + E)	Yes (deep recursion)	No	Preferred DFS approach to code
3. BFS Topological Sort (Kahn's Algorithm)	O(V + E)	O(V + E)	No	Yes (can output order)	Preferred BFS approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, and progressively discuss better solutions. Practice coding and testing each approach.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force DFS approach with recursion stack for cycle detection.Discuss the improved DFS with three-state coloring for clarity and efficiency.Present the BFS topological sort approach using in-degree counting.Code the preferred approach and test with sample inputs.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of graph cycle detection, ability to optimize DFS, knowledge of topological sorting, and coding accuracy under constraints.

Common Follow-ups

• How to return a valid order of courses? → Use topological sort to output order.
• What if the graph is very large? → Use BFS topological sort for better stack safety.

💡 Follow-ups often test your ability to extend cycle detection to course ordering and handle large inputs efficiently.

🔍

Pattern Recognition

When to Use

1) Problem involves prerequisites or dependencies; 2) Directed graph context; 3) Need to detect if all tasks can be completed; 4) Cycle detection is key.

Signature Phrases

can you finish all coursesprerequisite pairsdetect cycle in directed graph

NOT This Pattern When

Undirected graph cycle detection problems, shortest path problems, or undirected connectivity problems

Similar Problems

Detect Cycle in Directed Graph - core cycle detection problemMinimum Height Trees - uses topological trimming similar to Kahn's algorithmAlien Dictionary - topological sort to determine character order

Practice

1. Given the following Python code snippet implementing the BFS approach for Pacific Atlantic Water Flow, and the input heights = [[1,2,2],[3,2,3],[2,4,5]], what is the value of pacific_reachable after initializing the queues and marking the border cells?

easy

A. [[True, True, True], [True, False, False], [True, False, False]]

B. [[True, True, True], [True, False, False], [True, False, True]]

C. [[True, True, True], [False, False, False], [True, False, False]]

D. [[True, False, True], [True, False, False], [True, False, False]]

Solution

1. Step 1: Mark Pacific border cells

   Pacific borders are first row and first column. So pacific_reachable[0][j] and pacific_reachable[i][0] are True.

2. Step 2: Fill pacific_reachable matrix

   For m=3, n=3, first row and first column cells are True, others False initially.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First row and first column are True, rest False [OK]

Hint: Pacific reachable True on top row and left column [OK]

Common Mistakes:

• Forgetting to mark all border cells
• Marking wrong cells True

2. Given the following DFS-based code for rotting oranges, what is the value of max_time after processing the grid [[2,1,1],[1,1,0],[0,1,1]]?

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    time_grid = [[-1]*cols for _ in range(rows)]
    max_time = 0

    def dfs(r, c, time):
        nonlocal max_time
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == 0:
            return
        if time_grid[r][c] != -1 and time_grid[r][c] <= time:
            return
        time_grid[r][c] = time
        max_time = max(max_time, time)
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 1 or (grid[nr][nc] == 2 and time_grid[nr][nc] > time + 1):
                    dfs(nr, nc, time + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                dfs(r, c, 0)
    return max_time

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace DFS from rotten orange at (0,0) with time=0

   It rots adjacent fresh oranges incrementally, updating time_grid and max_time as rot spreads.

2. Step 2: Follow rot spread minute by minute

   Rot spreads to (0,1) and (1,0) at time=1, then to (0,2), (1,1), and (2,1) at time=2, and finally to (2,2) at time=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Maximum rot time matches the longest path from initial rotten orange [OK]

Hint: Max time equals longest rot spread path [OK]

Common Mistakes:

• Off-by-one counting minutes
• Ignoring multiple rotten sources
• Confusing grid indices

3. Consider the following Python code implementing bidirectional BFS to find the shortest path in a binary matrix. Given the input grid below, what is the returned shortest path length?

grid = [
  [0, 1, 0],
  [1, 0, 0],
  [1, 1, 0]
]

# Code snippet uses the bidirectional BFS approach as described.

What is the output of shortestPathBinaryMatrix(grid)?

easy

A. 3

B. 5

C. -1

D. 4

Solution

1. Step 1: Trace BFS from start (0,0)

   Start at (0,0) with distance 1. Neighbors reachable: (1,1) at distance 2.

2. Step 2: Trace BFS from end (2,2)

   Start at (2,2) with distance 1. Neighbors reachable: (1,2) at distance 2, (1,1) at distance 2.

3. Step 3: Meeting point

   Both searches meet at (1,1). Sum distances: 2 (start side) + 2 (end side) = 4, but since both include the meeting cell, shortest path length is 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest path length is 3 steps [OK]

Hint: Bidirectional BFS meets in middle, sum distances minus 1 [OK]

Common Mistakes:

• Off-by-one in path length
• Ignoring meeting cell counted twice

4. 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

5. The following code attempts to implement bidirectional BFS for Word Ladder. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.

medium

A. Line checking if next_word in end_set to return level + 1

B. Line swapping begin_set and end_set when begin_set is larger

C. Line adding next_word to next_level and visited

D. Line initializing visited with only beginWord

Solution

1. Step 1: Examine initialization of visited set

   Visited is initialized with only beginWord, but endWord is also in end_set and should be marked visited to avoid revisiting.

2. Step 2: Consequences of missing endWord in visited

   Without marking endWord visited, the algorithm may revisit it, causing cycles or incorrect early termination.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Visited must include both beginWord and endWord [OK]

Hint: Visited must include both ends to prevent cycles [OK]

Common Mistakes:

• Forgetting to mark endWord visited
• Swapping frontiers incorrectly
• Returning too early on neighbor match