Course Schedule II (Topological Order)

🎯

Course Schedule II (Topological Order)

mediumGRAPHAmazonFacebookGoogle

Imagine you are planning your semester courses, but some courses require you to finish others first. How do you find a valid order to take all courses?

💡 This problem is about ordering tasks with dependencies. Beginners often struggle because they try to find an order without considering cycles or dependencies properly. Understanding topological sort helps solve such dependency ordering problems.

📋

Problem Statement

Given the total number of courses numCourses and a list of prerequisite pairs prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i before course a_i, return the ordering of courses you should take to finish all courses. If there are multiple valid orders, return any of them. If it is impossible to finish all courses, return an empty array.

1 ≤ numCourses ≤ 10^50 ≤ prerequisites.length ≤ 10^5prerequisites[i].length == 20 ≤ a_i, b_i < numCourses

💡

Example

Input"numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]"

Output[0,1,2,3]

You must take course 0 before 1 and 2, and courses 1 and 2 before 3. One valid order is [0,1,2,3].

• No prerequisites → output can be any order of courses
• Single course with no prerequisites → output is that course
• Cycle in prerequisites → output is empty array
• Multiple disconnected components → output includes all courses in a valid order

⚠️

Common Mistakes

Not detecting cycles properly

Returns an invalid order or infinite loop

✅ Use visited states in DFS or check if all nodes processed in Kahn's algorithm

Incorrectly building adjacency list (reversing edges)

Order does not respect prerequisites

✅ Ensure edges go from prerequisite to dependent course

Modifying in-degree incorrectly or forgetting to decrement

Queue never updates correctly, causing infinite loop or wrong order

✅ Decrement in-degree for neighbors when a course is completed

Returning order without reversing in DFS approach

Order is reversed and invalid

✅ Reverse the order list before returning

Not handling disconnected components

Some courses missing from output

✅ Run DFS or enqueue all nodes with zero in-degree, including disconnected ones

🧠

Brute Force (Backtracking with Cycle Detection)

💡 This approach tries all possible orders recursively and checks if they satisfy prerequisites. It is very slow but helps understand the problem deeply and why more efficient methods are needed.

Intuition

Try every possible course order and verify if it respects all prerequisites. If a cycle is detected, backtrack and try another order.

Algorithm

1. Generate all permutations of courses.
2. For each permutation, check if it satisfies all prerequisite pairs.
3. If a permutation satisfies all prerequisites, return it as the valid order.
4. If no permutation works, return an empty array.

💡 The brute force method is straightforward but inefficient because it tries every possible order without pruning.

</>

Code

from itertools import permutations

def findOrder(numCourses, prerequisites):
    prereq_set = set((a, b) for a, b in prerequisites)
    for order in permutations(range(numCourses)):
        if all((a, b) not in prereq_set or order.index(b) < order.index(a) for a, b in prerequisites):
            return list(order)
    return []

# Driver code
if __name__ == '__main__':
    print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Line Notes

from itertools import permutationsImport permutations to generate all possible course orders

prereq_set = set((a, b) for a, b in prerequisites)Convert prerequisites to a set for O(1) lookup

for order in permutations(range(numCourses))Try every possible ordering of courses

if all((a, b) not in prereq_set or order.index(b) < order.index(a) for a, b in prerequisites)Check if current order respects all prerequisites

import java.util.*;

public class Solution {
    public List<Integer> findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> res = new ArrayList<>();
        List<Integer> courses = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) courses.add(i);
        if (permute(courses, 0, prerequisites, res)) return res;
        return new ArrayList<>();
    }

    private boolean permute(List<Integer> courses, int start, int[][] prerequisites, List<Integer> res) {
        if (start == courses.size()) {
            if (validOrder(courses, prerequisites)) {
                res.addAll(courses);
                return true;
            }
            return false;
        }
        for (int i = start; i < courses.size(); i++) {
            Collections.swap(courses, i, start);
            if (permute(courses, start + 1, prerequisites, res)) return true;
            Collections.swap(courses, i, start);
        }
        return false;
    }

    private boolean validOrder(List<Integer> order, int[][] prerequisites) {
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = 0; i < order.size(); i++) pos.put(order.get(i), i);
        for (int[] pre : prerequisites) {
            if (pos.get(pre[1]) >= pos.get(pre[0])) return false;
        }
        return true;
    }

    // Driver
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}}));
    }
}

Line Notes

for (int i = 0; i < numCourses; i++) courses.add(i);Initialize list of courses to permute

if (permute(courses, 0, prerequisites, res)) return res;Start recursive permutation and return if valid order found

Collections.swap(courses, i, start);Swap elements to generate permutations

if (pos.get(pre[1]) >= pos.get(pre[0])) return false;Check if prerequisite order is violated

#include <bits/stdc++.h>
using namespace std;

bool validOrder(const vector<int>& order, const vector<pair<int,int>>& prerequisites) {
    unordered_map<int,int> pos;
    for (int i = 0; i < (int)order.size(); i++) pos[order[i]] = i;
    for (auto& pre : prerequisites) {
        if (pos[pre.second] >= pos[pre.first]) return false;
    }
    return true;
}

bool permute(vector<int>& courses, int start, const vector<pair<int,int>>& prerequisites, vector<int>& res) {
    if (start == (int)courses.size()) {
        if (validOrder(courses, prerequisites)) {
            res = courses;
            return true;
        }
        return false;
    }
    for (int i = start; i < (int)courses.size(); i++) {
        swap(courses[i], courses[start]);
        if (permute(courses, start + 1, prerequisites, res)) return true;
        swap(courses[i], courses[start]);
    }
    return false;
}

vector<int> findOrder(int numCourses, vector<pair<int,int>> prerequisites) {
    vector<int> courses(numCourses);
    iota(courses.begin(), courses.end(), 0);
    vector<int> res;
    if (permute(courses, 0, prerequisites, res)) return res;
    return {};
}

int main() {
    vector<pair<int,int>> prereq = {{1,0},{2,0},{3,1},{3,2}};
    vector<int> order = findOrder(4, prereq);
    for (int c : order) cout << c << ' ';
    cout << '\n';
    return 0;
}

Line Notes

iota(courses.begin(), courses.end(), 0);Initialize courses vector with 0 to numCourses-1

swap(courses[i], courses[start]);Generate permutations by swapping elements

if (validOrder(courses, prerequisites)) {Check if current permutation respects prerequisites

pos[pre.second] >= pos[pre.first]Detect if prerequisite order is violated

function findOrder(numCourses, prerequisites) {
    function* permute(arr, l = 0) {
        if (l === arr.length) yield arr.slice();
        else {
            for (let i = l; i < arr.length; i++) {
                [arr[l], arr[i]] = [arr[i], arr[l]];
                yield* permute(arr, l + 1);
                [arr[l], arr[i]] = [arr[i], arr[l]];
            }
        }
    }

    function validOrder(order) {
        const pos = new Map();
        order.forEach((c, i) => pos.set(c, i));
        for (const [a, b] of prerequisites) {
            if (pos.get(b) >= pos.get(a)) return false;
        }
        return true;
    }

    const courses = Array.from({length: numCourses}, (_, i) => i);
    for (const order of permute(courses)) {
        if (validOrder(order)) return order;
    }
    return [];
}

// Driver
console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]));

Line Notes

function* permute(arr, l = 0)Generator function to yield all permutations recursively

[arr[l], arr[i]] = [arr[i], arr[l]];Swap elements to generate permutations

const pos = new Map();Map to store position of each course in current order

if (pos.get(b) >= pos.get(a)) return false;Check if prerequisite order is violated

⏱

Complexity

TimeO(n! * p * n) where n is numCourses and p is number of prerequisites

SpaceO(n) for recursion stack and permutations

We generate all permutations (n!) and for each, check all prerequisites (p) with index lookups (O(n))

💡 For n=4, this means 24 permutations to check, which is manageable, but for n=10, 3.6 million permutations make it infeasible.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why we need efficient algorithms.

🧠

DFS Based Topological Sort with Cycle Detection

💡 This approach uses depth-first search to order courses and detect cycles. It is more efficient than brute force and introduces the concept of visiting states to detect cycles.

Intuition

Perform DFS on each course, marking nodes as visiting and visited. If we revisit a visiting node, a cycle exists. Otherwise, add nodes to the order after visiting all dependencies.

Algorithm

1. Initialize adjacency list from prerequisites.
2. Create a visited array with states: 0 (unvisited), 1 (visiting), 2 (visited).
3. For each course, if unvisited, perform DFS:
4. - Mark as visiting.
5. - Recursively DFS neighbors.
6. - If a neighbor is visiting, cycle detected → return failure.
7. - Mark as visited and add to order.
8. Reverse the order list to get the topological order.

💡 The key is marking nodes during DFS to detect cycles and adding nodes post DFS to build order.

</>

Code

def findOrder(numCourses, prerequisites):
    from collections import defaultdict
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)

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

    def dfs(node):
        if visited[node] == 1:
            return False  # cycle detected
        if visited[node] == 2:
            return True
        visited[node] = 1
        for nei in graph[node]:
            if not dfs(nei):
                return False
        visited[node] = 2
        order.append(node)
        return True

    for i in range(numCourses):
        if visited[i] == 0:
            if not dfs(i):
                return []
    return order[::-1]

# Driver
if __name__ == '__main__':
    print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Line Notes

graph = defaultdict(list)Build adjacency list for graph representation

visited = [0] * numCoursesTrack visit state of each node to detect cycles

if visited[node] == 1:Detect cycle if node is currently being visited

order.append(node)Add node to order after visiting all dependencies

import java.util.*;

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

        int[] visited = new int[numCourses]; // 0=unvisited,1=visiting,2=visited
        List<Integer> order = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(i, graph, visited, order)) return new int[0];
            }
        }

        Collections.reverse(order);
        return order.stream().mapToInt(i -> i).toArray();
    }

    private boolean dfs(int node, List<List<Integer>> graph, int[] visited, List<Integer> order) {
        if (visited[node] == 1) return false;
        if (visited[node] == 2) return true;
        visited[node] = 1;
        for (int nei : graph.get(node)) {
            if (!dfs(nei, graph, visited, order)) return false;
        }
        visited[node] = 2;
        order.add(node);
        return true;
    }

    // Driver
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}})));
    }
}

Line Notes

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

int[] visited = new int[numCourses];Track node states for cycle detection

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

order.add(node);Add node to order after all dependencies processed

#include <bits/stdc++.h>
using namespace std;

bool dfs(int node, vector<vector<int>>& graph, vector<int>& visited, vector<int>& order) {
    if (visited[node] == 1) return false;
    if (visited[node] == 2) return true;
    visited[node] = 1;
    for (int nei : graph[node]) {
        if (!dfs(nei, graph, visited, order)) return false;
    }
    visited[node] = 2;
    order.push_back(node);
    return true;
}

vector<int> findOrder(int numCourses, vector<pair<int,int>> prerequisites) {
    vector<vector<int>> graph(numCourses);
    for (auto& pre : prerequisites) graph[pre.second].push_back(pre.first);
    vector<int> visited(numCourses, 0);
    vector<int> order;
    for (int i = 0; i < numCourses; i++) {
        if (visited[i] == 0) {
            if (!dfs(i, graph, visited, order)) return {};
        }
    }
    reverse(order.begin(), order.end());
    return order;
}

int main() {
    vector<pair<int,int>> prereq = {{1,0},{2,0},{3,1},{3,2}};
    vector<int> order = findOrder(4, prereq);
    for (int c : order) cout << c << ' ';
    cout << '\n';
    return 0;
}

Line Notes

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

vector<int> visited(numCourses, 0);Track visit states for cycle detection

if (visited[node] == 1) return false;Detect cycle if node is currently visiting

order.push_back(node);Add node to order after visiting dependencies

function findOrder(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    for (const [a, b] of prerequisites) graph[b].push(a);

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

    function dfs(node) {
        if (visited[node] === 1) return false;
        if (visited[node] === 2) return true;
        visited[node] = 1;
        for (const nei of graph[node]) {
            if (!dfs(nei)) return false;
        }
        visited[node] = 2;
        order.push(node);
        return true;
    }

    for (let i = 0; i < numCourses; i++) {
        if (visited[i] === 0) {
            if (!dfs(i)) return [];
        }
    }
    return order.reverse();
}

// Driver
console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]));

Line Notes

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

const visited = new Array(numCourses).fill(0);Track node states for cycle detection

if (visited[node] === 1) return false;Detect cycle if node is currently visiting

order.push(node);Add node to order after all dependencies processed

⏱

Complexity

TimeO(V + E) where V is number of courses and E is number of prerequisites

SpaceO(V + E) for graph and recursion stack

Each node and edge is visited once during DFS traversal

💡 For 1000 courses and 2000 prerequisites, this approach efficiently handles the input within milliseconds.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for topological sorting with cycle detection.

🧠

Kahn's Algorithm (BFS / In-Degree Based Topological Sort)

💡 Kahn's algorithm uses BFS and in-degree counts to find a valid course order. It is intuitive and often preferred in interviews for its clarity and efficiency.

Intuition

Count how many prerequisites each course has (in-degree). Start with courses having zero prerequisites. Remove them and reduce in-degree of dependent courses. Repeat until all courses are processed or a cycle is detected.

Algorithm

1. Build adjacency list and compute in-degree for each course.
2. Initialize a queue with all courses having in-degree zero.
3. While queue is not empty:
4. - Pop a course from queue and add it to the order.
5. - For each neighbor, decrement its in-degree.
6. - If in-degree of neighbor becomes zero, add it to queue.
7. If order contains all courses, return order; otherwise, return empty array.

💡 This approach processes courses layer by layer, ensuring prerequisites are met before taking dependent courses.

</>

Code

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

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

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

    if len(order) == numCourses:
        return order
    else:
        return []

# Driver
if __name__ == '__main__':
    print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Line Notes

graph = defaultdict(list)Build adjacency list for graph representation

in_degree = [0] * numCoursesTrack number of prerequisites for each course

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

in_degree[nei] -= 1Decrement in-degree when a prerequisite course is completed

import java.util.*;

public class Solution {
    public int[] findOrder(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[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

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

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int nei : graph.get(node)) {
                inDegree[nei]--;
                if (inDegree[nei] == 0) queue.offer(nei);
            }
        }

        if (order.size() == numCourses) {
            return order.stream().mapToInt(i -> i).toArray();
        } else {
            return new int[0];
        }
    }

    // Driver
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}})));
    }
}

Line Notes

int[] inDegree = new int[numCourses];Array to count prerequisites for each course

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

inDegree[nei]--;Reduce in-degree after completing a prerequisite

if (order.size() == numCourses)Check if all courses are included in the order

#include <bits/stdc++.h>
using namespace std;

vector<int> findOrder(int numCourses, vector<pair<int,int>> prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> inDegree(numCourses, 0);
    for (auto& pre : prerequisites) {
        graph[pre.second].push_back(pre.first);
        inDegree[pre.first]++;
    }

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

    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int nei : graph[node]) {
            inDegree[nei]--;
            if (inDegree[nei] == 0) q.push(nei);
        }
    }

    if ((int)order.size() == numCourses) return order;
    return {};
}

int main() {
    vector<pair<int,int>> prereq = {{1,0},{2,0},{3,1},{3,2}};
    vector<int> order = findOrder(4, prereq);
    for (int c : order) cout << c << ' ';
    cout << '\n';
    return 0;
}

Line Notes

vector<int> inDegree(numCourses, 0);Track number of prerequisites for each course

if (inDegree[i] == 0) q.push(i);Start with courses that have no prerequisites

inDegree[nei]--;Decrement in-degree after processing a prerequisite

if ((int)order.size() == numCourses)Verify if all courses are included in the order

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

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

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

    return order.length === numCourses ? order : [];
}

// Driver
console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]));

Line Notes

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

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

inDegree[nei]--;Decrease in-degree after completing a prerequisite

return order.length === numCourses ? order : [];Return order if all courses included, else empty array

⏱

Complexity

TimeO(V + E) where V is number of courses and E is number of prerequisites

SpaceO(V + E) for graph, in-degree array, and queue

Each course and prerequisite edge is processed once during BFS

💡 For 100,000 courses and prerequisites, this approach scales efficiently and is practical for real-world problems.

Interview Verdict: Accepted

Kahn's algorithm is optimal and preferred for topological sorting in interviews due to its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Kahn's algorithm is the best choice for interviews due to its clarity and efficiency. DFS is also acceptable. Brute force is only for conceptual understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * p * n)	O(n)	Yes (deep recursion in permutations)	Yes	Mention only - never code
2. DFS Topological Sort	O(V + E)	O(V + E)	Possible (deep recursion)	Yes	Good to code if comfortable with recursion
3. Kahn's Algorithm (BFS)	O(V + E)	O(V + E)	No	Yes	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of the problem.Step 3: Explain DFS-based topological sort with cycle detection.Step 4: Present Kahn's algorithm as the optimal BFS solution.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal, cycle detection, and ability to implement topological sort efficiently.

Common Follow-ups

• What if there are multiple valid orders? → Return any valid order.
• How to detect if no valid order exists? → Detect cycle via DFS or if not all nodes processed in Kahn's.

💡 These follow-ups check your grasp of problem nuances and edge cases.

🔍

Pattern Recognition

When to Use

1) Problem involves ordering tasks with dependencies, 2) Need to detect cycles, 3) Input can be represented as a directed graph, 4) Output is a linear ordering of nodes.

Signature Phrases

must take course beforeprerequisite pairsreturn orderingimpossible to finish all courses

NOT This Pattern When

Problems involving undirected graphs or shortest paths are different patterns.

Similar Problems

Course Schedule I - checks if possible to finish courses (boolean)Alien Dictionary - find character order from dictionaryMinimum Height Trees - find roots with minimal height in graph

Practice

1. Given the following code snippet implementing topological sort positions, what is the final value of the pos array after processing conditions = [[1,2],[1,3],[3,4]] with n=4?

easy

A. [0, 0, 1, 2, 3]

B. [0, 0, 2, 1, 3]

C. [0, 0, 1, 3, 2]

D. [0, 1, 2, 3, 0]

Solution

1. Step 1: Initialize graph and in-degree arrays

   Edges: 1->2, 1->3, 3->4; in_degree: [0,0,1,1,1]

2. Step 2: Process queue and assign positions

   Queue starts with node 1 (in_degree 0). Assign pos[1]=0. Decrement in_degree of 2 and 3 to 0, enqueue both. Next, dequeue 2 (pos[2]=1), then dequeue 3 (pos[3]=2), decrement in_degree of 4 to 0, enqueue 4, assign pos[4]=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Positions reflect valid topological order [OK]

Hint: Track in-degree and queue order carefully [OK]

Common Mistakes:

• Swapping positions of nodes 2 and 3
• Off-by-one indexing in pos array

2. Consider the following buggy code snippet for the alien dictionary problem. Which line contains the subtle bug that can cause incorrect results on inputs where a word is a prefix of the next word?

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        # BUG: Missing prefix invalid case check here
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

medium

A. Line missing prefix invalid case check before edge addition

B. Line initializing in_degree dictionary

C. Line checking if w1[j] != w2[j] to add edge

D. Line decrementing in_degree of neighbors in BFS loop

Solution

1. Step 1: Identify prefix invalid case

   If a longer word is prefix of a shorter next word (e.g., "abc" before "ab"), the order is invalid and must return "".

2. Step 2: Locate missing check

   The code lacks the check: if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]: return "" before adding edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing prefix check causes incorrect order or silent failure [OK]

Hint: Prefix invalid case must be checked before edge addition [OK]

Common Mistakes:

• Ignoring prefix invalid case leads to wrong output
• Misplacing in-degree initialization
• Incorrectly decrementing in-degree in BFS

3. What is the time complexity of the optimal approach that uses the reversed graph and Kahn's algorithm to find eventual safe states in a graph with V vertices and E edges?

medium

A. O(V + E) because each edge and vertex is processed once during graph reversal and BFS

B. O(V^2) because we process each node and its neighbors repeatedly

C. O(V * E) due to nested loops over vertices and edges

D. O(E log V) because of sorting the safe nodes at the end

Solution

1. Step 1: Analyze graph reversal and in-degree computation

   Reversing the graph and computing in-degree requires iterating over all edges once, O(E).

2. Step 2: Analyze BFS processing

   Each node is enqueued and dequeued at most once, and each edge is considered once when decrementing in-degree, total O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in vertices and edges matches BFS and graph reversal [OK]

Hint: Each edge and vertex processed once in BFS + reversal [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing sorting cost as dominant
• Forgetting BFS processes each edge once

4. Suppose the problem is modified so that nodes can be revisited multiple times (cycles allowed). Which modification to the iterative DFS approach is necessary to correctly find all paths from source to target without infinite loops?

hard

A. Add a visited set per path to prevent revisiting nodes already in the current path

B. Remove path tracking and rely on global visited set to avoid cycles

C. Use BFS instead of DFS to guarantee shortest paths and avoid cycles

D. No modification needed; the current approach handles cycles correctly

Solution

1. Step 1: Identify cycle problem

   Allowing revisits means cycles can cause infinite loops if not tracked per path.

2. Step 2: Solution approach

   Maintain a visited set per path to avoid revisiting nodes already in the current path, preventing cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Global visited set disallows legitimate different paths; per-path visited set is needed [OK]

Hint: Cycle detection requires per-path visited tracking, not global visited [OK]

Common Mistakes:

• Using global visited set incorrectly
• Assuming no cycles without checks

5. Suppose the problem is modified so that elements in the sequences can be reused multiple times (i.e., sequences may contain repeated elements). Which of the following changes to the DFS postorder topological sort approach is necessary to correctly determine if the original sequence can be uniquely reconstructed?

hard

A. No changes needed; the existing DFS approach handles repeated elements naturally.

B. Modify graph construction to allow multiple edges between the same nodes and adjust cycle detection accordingly.

C. Switch to BFS topological sort with a queue that tracks in-degree counts considering repeated edges.

D. Preprocess sequences to remove duplicates before building the graph, then run the original DFS approach.

Solution

1. Step 1: Understand impact of repeated elements

   Repeated elements mean multiple edges between same nodes may exist, affecting graph structure and cycle detection.

2. Step 2: Adjust graph and DFS accordingly

   Graph must allow multiple edges or count edge multiplicity; cycle detection must consider these to avoid false negatives or infinite recursion.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Handling repeated edges is essential for correctness with reused elements [OK]

Hint: Repeated elements require multi-edge aware graph and cycle detection [OK]

Common Mistakes:

• Assuming no changes needed
• Removing duplicates loses info
• Switching to BFS without handling repeats