Parallel Courses (Minimum Semesters)

🎯

Parallel Courses (Minimum Semesters)

mediumGRAPHAmazonGoogleFacebook

Imagine you are planning your university semesters and want to finish all your courses in the minimum number of semesters possible, respecting prerequisite constraints.

💡 This problem involves scheduling tasks with dependencies, which is a classic graph problem. Beginners often struggle because they don't immediately recognize that the problem can be modeled as a directed graph and solved using topological sorting.

📋

Problem Statement

You are given an integer n representing the number of courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship: course prevCourse_i must be taken before course nextCourse_i. In one semester, you can take any number of courses as long as all their prerequisites are met. Return the minimum number of semesters needed to take all courses. If it is impossible to finish all courses, return -1.

1 ≤ n ≤ 10^51 ≤ relations.length ≤ 5 * 10^5relations[i].length == 21 ≤ prevCourse_i, nextCourse_i ≤ nprevCourse_i != nextCourse_i

💡

Example

Input"n = 3, relations = [[1,3],[2,3]]"

Output2

Courses 1 and 2 can be taken in the first semester, and course 3 in the second semester.

Input"n = 3, relations = [[1,2],[2,3],[3,1]]"

Output-1

There is a cycle in the prerequisites, so it's impossible to finish all courses.

• No prerequisites (relations is empty) → minimum semesters is 1
• Single course with no prerequisites → minimum semesters is 1
• Cycle in prerequisites → return -1
• Large number of courses with linear chain prerequisites → semesters equals number of courses

⚠️

Common Mistakes

Not detecting cycles and returning incorrect semester count

Returns a number even when courses can't be completed

✅ Track number of processed courses and compare with total courses to detect cycles

Processing courses one by one instead of level by level

Incorrect semester count as parallel courses are not accounted for

✅ Process all courses with indegree 0 in the same BFS level to represent one semester

Modifying indegree array without copying in recursive approaches

Incorrect indegree values leading to wrong results or infinite loops

✅ Use copies of indegree array when backtracking or carefully restore after recursion

Not initializing indegree or graph correctly for all courses

Missing courses or wrong prerequisites cause incorrect output

✅ Initialize graph and indegree arrays for all courses from 1 to n

Using 0-based indexing inconsistently with 1-based course labels

Index errors or wrong course processing

✅ Be consistent with indexing; usually use 1-based indexing for courses

🧠

Brute Force (Backtracking with Cycle Detection)

💡 This approach tries all possible orders of taking courses to find the minimum semesters. It is extremely inefficient but helps understand the problem deeply and why we need better methods.

Intuition

Try every possible sequence of courses respecting prerequisites and count semesters. If a cycle is detected, return -1.

Algorithm

1. Build a graph from the relations.
2. Use backtracking to try all possible course orders that respect prerequisites.
3. Keep track of courses taken and semesters used.
4. If all courses are taken, update the minimum semesters; if a cycle is detected, return -1.

💡 This algorithm is hard because it tries all permutations and must carefully check prerequisites and cycles, which is exponential in time.

</>

Code

from collections import defaultdict

def min_semesters_brute_force(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    min_semesters = [float('inf')]

    def backtrack(taken, indeg, semester):
        if len(taken) == n:
            min_semesters[0] = min(min_semesters[0], semester)
            return
        # Find all courses with indegree 0 and not taken
        available = [i for i in range(1, n + 1) if indeg[i] == 0 and i not in taken]
        if not available:
            return
        # Try all subsets of available courses (simulate parallel courses)
        # For brute force, try taking each course individually (to keep it simple)
        for course in available:
            taken.add(course)
            new_indeg = indeg[:]
            for nei in graph[course]:
                new_indeg[nei] -= 1
            backtrack(taken, new_indeg, semester + 1)
            taken.remove(course)

    backtrack(set(), indegree, 0)
    return min_semesters[0] if min_semesters[0] != float('inf') else -1

# Example usage
if __name__ == '__main__':
    print(min_semesters_brute_force(3, [[1,3],[2,3]]))  # Output: 2
    print(min_semesters_brute_force(3, [[1,2],[2,3],[3,1]]))  # Output: -1

Line Notes

graph = defaultdict(list)Initialize adjacency list to represent course dependencies

indegree = [0] * (n + 1)Track number of prerequisites for each course

for u, v in relations:Build graph and indegree array from relations

def backtrack(taken, indeg, semester):Recursive function to try all course taking sequences

available = [i for i in range(1, n + 1) if indeg[i] == 0 and i not in taken]Find courses ready to be taken this semester

for course in available:Try taking each available course individually to simulate parallelism

taken.add(course)Mark course as taken

new_indeg = indeg[:]Copy indegree array to update for next recursion

for nei in graph[course]:Decrease indegree of dependent courses after taking current course

backtrack(taken, new_indeg, semester + 1)Recurse to next semester after taking a course

taken.remove(course)Backtrack to try other course combinations

import java.util.*;

public class ParallelCoursesBruteForce {
    static int n;
    static List<List<Integer>> graph;
    static int[] indegree;
    static int minSemesters = Integer.MAX_VALUE;

    public static int minSemestersBruteForce(int courses, int[][] relations) {
        n = courses;
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        indegree = new int[n + 1];
        for (int[] rel : relations) {
            graph.get(rel[0]).add(rel[1]);
            indegree[rel[1]]++;
        }
        backtrack(new HashSet<>(), indegree, 0);
        return minSemesters == Integer.MAX_VALUE ? -1 : minSemesters;
    }

    private static void backtrack(Set<Integer> taken, int[] indeg, int semester) {
        if (taken.size() == n) {
            minSemesters = Math.min(minSemesters, semester);
            return;
        }
        List<Integer> available = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0 && !taken.contains(i)) available.add(i);
        }
        if (available.isEmpty()) return;
        for (int course : available) {
            taken.add(course);
            int[] newIndeg = indeg.clone();
            for (int nei : graph.get(course)) newIndeg[nei]--;
            backtrack(taken, newIndeg, semester + 1);
            taken.remove(course);
        }
    }

    public static void main(String[] args) {
        System.out.println(minSemestersBruteForce(3, new int[][]{{1,3},{2,3}})); // 2
        System.out.println(minSemestersBruteForce(3, new int[][]{{1,2},{2,3},{3,1}})); // -1
    }
}

Line Notes

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

indegree = new int[n + 1]Array to count prerequisites for each course

for (int[] rel : relations)Build graph and indegree from input relations

backtrack(new HashSet<>(), indegree, 0)Start backtracking with empty taken set and initial indegree

List<Integer> available = new ArrayList<>()Find courses with no remaining prerequisites

for (int course : available)Try taking each available course individually

int[] newIndeg = indeg.clone()Clone indegree array to update for recursion

for (int nei : graph.get(course)) newIndeg[nei]--Decrease indegree of dependent courses after taking current course

backtrack(taken, newIndeg, semester + 1)Recurse to next semester

taken.remove(course)Backtrack to try other options

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

int n;
vector<vector<int>> graph;
int minSemesters = INT_MAX;

void backtrack(unordered_set<int>& taken, vector<int>& indeg, int semester) {
    if ((int)taken.size() == n) {
        minSemesters = min(minSemesters, semester);
        return;
    }
    vector<int> available;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0 && taken.find(i) == taken.end()) available.push_back(i);
    }
    if (available.empty()) return;
    for (int course : available) {
        taken.insert(course);
        vector<int> newIndeg = indeg;
        for (int nei : graph[course]) newIndeg[nei]--;
        backtrack(taken, newIndeg, semester + 1);
        taken.erase(course);
    }
}

int minSemestersBruteForce(int courses, vector<pair<int,int>>& relations) {
    n = courses;
    graph.assign(n + 1, vector<int>());
    vector<int> indeg(n + 1, 0);
    for (auto& rel : relations) {
        graph[rel.first].push_back(rel.second);
        indeg[rel.second]++;
    }
    unordered_set<int> taken;
    backtrack(taken, indeg, 0);
    return minSemesters == INT_MAX ? -1 : minSemesters;
}

int main() {
    vector<pair<int,int>> rel1 = {{1,3},{2,3}};
    cout << minSemestersBruteForce(3, rel1) << "\n"; // 2
    vector<pair<int,int>> rel2 = {{1,2},{2,3},{3,1}};
    cout << minSemestersBruteForce(3, rel2) << "\n"; // -1
    return 0;
}

Line Notes

graph.assign(n + 1, vector<int>())Initialize adjacency list for graph

vector<int> indeg(n + 1, 0)Indegree array to count prerequisites

for (auto& rel : relations)Build graph and indegree from input

void backtrack(unordered_set<int>& taken, vector<int>& indeg, int semester)Recursive backtracking function

vector<int> availableFind courses with zero indegree and not taken

for (int course : available)Try taking each available course individually

vector<int> newIndeg = indegCopy indegree array for recursion

for (int nei : graph[course]) newIndeg[nei]--Update indegree after taking course

backtrack(taken, newIndeg, semester + 1)Recurse to next semester

taken.erase(course)Backtrack to try other options

function minSemestersBruteForce(n, relations) {
    const graph = Array.from({length: n + 1}, () => []);
    const indegree = Array(n + 1).fill(0);
    for (const [u, v] of relations) {
        graph[u].push(v);
        indegree[v]++;
    }
    let minSemesters = Infinity;

    function backtrack(taken, indeg, semester) {
        if (taken.size === n) {
            minSemesters = Math.min(minSemesters, semester);
            return;
        }
        const available = [];
        for (let i = 1; i <= n; i++) {
            if (indeg[i] === 0 && !taken.has(i)) available.push(i);
        }
        if (available.length === 0) return;
        for (const course of available) {
            taken.add(course);
            const newIndeg = indeg.slice();
            for (const nei of graph[course]) newIndeg[nei]--;
            backtrack(taken, newIndeg, semester + 1);
            taken.delete(course);
        }
    }

    backtrack(new Set(), indegree, 0);
    return minSemesters === Infinity ? -1 : minSemesters;
}

// Example usage
console.log(minSemestersBruteForce(3, [[1,3],[2,3]])); // 2
console.log(minSemestersBruteForce(3, [[1,2],[2,3],[3,1]])); // -1

Line Notes

const graph = Array.from({length: n + 1}, () => [])Initialize adjacency list for graph

const indegree = Array(n + 1).fill(0)Indegree array to track prerequisites

for (const [u, v] of relations)Build graph and indegree from input

function backtrack(taken, indeg, semester)Recursive backtracking function

const available = []Find courses with zero indegree and not taken

for (const course of available)Try taking each available course individually

const newIndeg = indeg.slice()Copy indegree array for recursion

for (const nei of graph[course]) newIndeg[nei]--Update indegree after taking course

backtrack(taken, newIndeg, semester + 1)Recurse to next semester

taken.delete(course)Backtrack to try other options

⏱

Complexity

TimeO(n!) in worst case due to trying all permutations

SpaceO(n) for recursion stack and bookkeeping

The brute force tries all sequences of courses respecting prerequisites, which is factorial in n, making it impractical for large inputs.

💡 For n=10, this approach could try up to 3,628,800 sequences, which is too large to finish in reasonable time.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Better Approach (Topological Sort with BFS - Kahn's Algorithm)

💡 This approach uses topological sorting to process courses level by level, representing semesters. It is efficient and directly models the problem constraints.

Intuition

Courses with no prerequisites can be taken in the first semester. After taking them, remove their edges and find new courses with no prerequisites for the next semester, repeating until all courses are taken or a cycle is detected.

Algorithm

1. Build the graph and indegree array from relations.
2. Initialize a queue with all courses having indegree 0 (no prerequisites).
3. While the queue is not empty, process all courses in the queue (one semester):
4. - For each course, reduce indegree of its neighbors.
5. - If any neighbor's indegree becomes 0, add it to the queue.
6. Increment semester count after processing each level.
7. If all courses are processed, return the semester count; otherwise, return -1.

💡 This algorithm is easier to understand because it processes courses in layers, each layer representing one semester.

</>

Code

from collections import deque, defaultdict

def min_semesters_kahn(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    semester = 0
    taken = 0

    while queue:
        semester += 1
        for _ in range(len(queue)):
            course = queue.popleft()
            taken += 1
            for nei in graph[course]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

    return semester if taken == n else -1

# Example usage
if __name__ == '__main__':
    print(min_semesters_kahn(3, [[1,3],[2,3]]))  # Output: 2
    print(min_semesters_kahn(3, [[1,2],[2,3],[3,1]]))  # Output: -1

Line Notes

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

indegree = [0] * (n + 1)Track number of prerequisites for each course

queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])Initialize queue with courses having no prerequisites

while queue:Process courses level by level (semester by semester)

semester += 1Increment semester count after processing each level

for _ in range(len(queue))Process all courses available in current semester

course = queue.popleft()Take one course from the queue

taken += 1Count courses taken so far

for nei in graph[course]:For each dependent course, reduce indegree

if indegree[nei] == 0: queue.append(nei)Add newly available courses to queue

import java.util.*;

public class ParallelCoursesKahn {
    public static int minSemestersKahn(int n, int[][] relations) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n + 1];
        for (int[] rel : relations) {
            graph.get(rel[0]).add(rel[1]);
            indegree[rel[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        int semester = 0, taken = 0;
        while (!queue.isEmpty()) {
            semester++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                taken++;
                for (int nei : graph.get(course)) {
                    indegree[nei]--;
                    if (indegree[nei] == 0) queue.offer(nei);
                }
            }
        }
        return taken == n ? semester : -1;
    }

    public static void main(String[] args) {
        System.out.println(minSemestersKahn(3, new int[][]{{1,3},{2,3}})); // 2
        System.out.println(minSemestersKahn(3, new int[][]{{1,2},{2,3},{3,1}})); // -1
    }
}

Line Notes

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

int[] indegree = new int[n + 1]Array to count prerequisites for each course

for (int[] rel : relations)Build graph and indegree from input

Queue<Integer> queue = new LinkedList<>()Queue for BFS traversal

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

while (!queue.isEmpty())Process courses semester by semester

semester++Increment semester count after processing current level

for (int i = 0; i < size; i++)Process all courses available this semester

indegree[nei]--Decrease indegree of dependent courses

if (indegree[nei] == 0) queue.offer(nei)Add newly available courses to queue

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

int minSemestersKahn(int n, vector<pair<int,int>>& relations) {
    vector<vector<int>> graph(n + 1);
    vector<int> indegree(n + 1, 0);
    for (auto& rel : relations) {
        graph[rel.first].push_back(rel.second);
        indegree[rel.second]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    int semester = 0, taken = 0;
    while (!q.empty()) {
        semester++;
        int size = (int)q.size();
        for (int i = 0; i < size; i++) {
            int course = q.front(); q.pop();
            taken++;
            for (int nei : graph[course]) {
                indegree[nei]--;
                if (indegree[nei] == 0) q.push(nei);
            }
        }
    }
    return taken == n ? semester : -1;
}

int main() {
    vector<pair<int,int>> rel1 = {{1,3},{2,3}};
    cout << minSemestersKahn(3, rel1) << "\n"; // 2
    vector<pair<int,int>> rel2 = {{1,2},{2,3},{3,1}};
    cout << minSemestersKahn(3, rel2) << "\n"; // -1
    return 0;
}

Line Notes

vector<vector<int>> graph(n + 1)Initialize adjacency list for graph

vector<int> indegree(n + 1, 0)Indegree array to track prerequisites

for (auto& rel : relations)Build graph and indegree from input

queue<int> qQueue for BFS traversal

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

while (!q.empty())Process courses semester by semester

semester++Increment semester count after processing current level

for (int i = 0; i < size; i++)Process all courses available this semester

indegree[nei]--Decrease indegree of dependent courses

if (indegree[nei] == 0) q.push(nei)Add newly available courses to queue

function minSemestersKahn(n, relations) {
    const graph = Array.from({length: n + 1}, () => []);
    const indegree = Array(n + 1).fill(0);
    for (const [u, v] of relations) {
        graph[u].push(v);
        indegree[v]++;
    }
    const queue = [];
    for (let i = 1; i <= n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    let semester = 0, taken = 0;
    while (queue.length > 0) {
        semester++;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const course = queue.shift();
            taken++;
            for (const nei of graph[course]) {
                indegree[nei]--;
                if (indegree[nei] === 0) queue.push(nei);
            }
        }
    }
    return taken === n ? semester : -1;
}

// Example usage
console.log(minSemestersKahn(3, [[1,3],[2,3]])); // 2
console.log(minSemestersKahn(3, [[1,2],[2,3],[3,1]])); // -1

Line Notes

const graph = Array.from({length: n + 1}, () => [])Initialize adjacency list for graph

const indegree = Array(n + 1).fill(0)Indegree array to track prerequisites

for (const [u, v] of relations)Build graph and indegree from input

const queue = []Queue for BFS traversal

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

while (queue.length > 0)Process courses semester by semester

semester++Increment semester count after processing current level

for (let i = 0; i < size; i++)Process all courses available this semester

indegree[nei]--Decrease indegree of dependent courses

if (indegree[nei] === 0) queue.push(nei)Add newly available courses to queue

⏱

Complexity

TimeO(n + m) where m is number of relations

SpaceO(n + m) for graph and indegree arrays

Each course and edge is processed once in BFS, making it efficient for large inputs.

💡 For n=100,000 and m=500,000, this approach can finish in seconds, unlike brute force.

Interview Verdict: Accepted

This is the standard and efficient solution for this problem in interviews.

🧠

Optimal Approach (Topological Sort with BFS + Early Cycle Detection)

💡 This approach is similar to the previous but explicitly tracks if a cycle exists by comparing processed courses count with total courses, allowing early termination.

Intuition

If after processing all possible courses the count is less than n, a cycle exists and we return -1 immediately.

Algorithm

1. Build graph and indegree array.
2. Initialize queue with courses having indegree 0.
3. Initialize semester count and processed courses count.
4. While queue not empty, process all courses in current semester:
5. - Decrement indegree of neighbors and enqueue if indegree becomes 0.
6. - Increment processed courses count.
7. If processed courses count equals n, return semester count; else return -1.

💡 This approach adds explicit cycle detection by counting processed courses, which is critical for correctness.

</>

Code

from collections import deque, defaultdict

def min_semesters_optimal(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    semester = 0
    processed = 0

    while queue:
        semester += 1
        for _ in range(len(queue)):
            course = queue.popleft()
            processed += 1
            for nei in graph[course]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

    return semester if processed == n else -1

# Example usage
if __name__ == '__main__':
    print(min_semesters_optimal(3, [[1,3],[2,3]]))  # Output: 2
    print(min_semesters_optimal(3, [[1,2],[2,3],[3,1]]))  # Output: -1

Line Notes

graph = defaultdict(list)Create adjacency list for graph

indegree = [0] * (n + 1)Track prerequisites count

queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])Initialize queue with courses ready to take

semester = 0Initialize semester counter

processed = 0Count of courses taken so far

while queue:Process courses semester by semester

semester += 1Increment semester after processing current level

processed += 1Increment count of courses taken

for nei in graph[course]:Update indegree of dependent courses

if indegree[nei] == 0: queue.append(nei)Add newly available courses to queue

import java.util.*;

public class ParallelCoursesOptimal {
    public static int minSemestersOptimal(int n, int[][] relations) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n + 1];
        for (int[] rel : relations) {
            graph.get(rel[0]).add(rel[1]);
            indegree[rel[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        int semester = 0, processed = 0;
        while (!queue.isEmpty()) {
            semester++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                processed++;
                for (int nei : graph.get(course)) {
                    indegree[nei]--;
                    if (indegree[nei] == 0) queue.offer(nei);
                }
            }
        }
        return processed == n ? semester : -1;
    }

    public static void main(String[] args) {
        System.out.println(minSemestersOptimal(3, new int[][]{{1,3},{2,3}})); // 2
        System.out.println(minSemestersOptimal(3, new int[][]{{1,2},{2,3},{3,1}})); // -1
    }
}

Line Notes

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

int[] indegree = new int[n + 1]Array to count prerequisites

Queue<Integer> queue = new LinkedList<>()Queue for BFS

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

int semester = 0, processed = 0Initialize counters

while (!queue.isEmpty())Process courses semester by semester

semester++Increment semester count

processed++Count courses taken

indegree[nei]--Decrease indegree of dependent courses

if (indegree[nei] == 0) queue.offer(nei)Add newly available courses

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

int minSemestersOptimal(int n, vector<pair<int,int>>& relations) {
    vector<vector<int>> graph(n + 1);
    vector<int> indegree(n + 1, 0);
    for (auto& rel : relations) {
        graph[rel.first].push_back(rel.second);
        indegree[rel.second]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    int semester = 0, processed = 0;
    while (!q.empty()) {
        semester++;
        int size = (int)q.size();
        for (int i = 0; i < size; i++) {
            int course = q.front(); q.pop();
            processed++;
            for (int nei : graph[course]) {
                indegree[nei]--;
                if (indegree[nei] == 0) q.push(nei);
            }
        }
    }
    return processed == n ? semester : -1;
}

int main() {
    vector<pair<int,int>> rel1 = {{1,3},{2,3}};
    cout << minSemestersOptimal(3, rel1) << "\n"; // 2
    vector<pair<int,int>> rel2 = {{1,2},{2,3},{3,1}};
    cout << minSemestersOptimal(3, rel2) << "\n"; // -1
    return 0;
}

Line Notes

vector<vector<int>> graph(n + 1)Initialize adjacency list

vector<int> indegree(n + 1, 0)Indegree array for prerequisites

queue<int> qQueue for BFS

if (indegree[i] == 0) q.push(i)Add courses with no prerequisites

int semester = 0, processed = 0Initialize counters

while (!q.empty())Process courses semester by semester

semester++Increment semester count

processed++Count courses taken

indegree[nei]--Decrease indegree of dependent courses

if (indegree[nei] == 0) q.push(nei)Add newly available courses

function minSemestersOptimal(n, relations) {
    const graph = Array.from({length: n + 1}, () => []);
    const indegree = Array(n + 1).fill(0);
    for (const [u, v] of relations) {
        graph[u].push(v);
        indegree[v]++;
    }
    const queue = [];
    for (let i = 1; i <= n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    let semester = 0, processed = 0;
    while (queue.length > 0) {
        semester++;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const course = queue.shift();
            processed++;
            for (const nei of graph[course]) {
                indegree[nei]--;
                if (indegree[nei] === 0) queue.push(nei);
            }
        }
    }
    return processed === n ? semester : -1;
}

// Example usage
console.log(minSemestersOptimal(3, [[1,3],[2,3]])); // 2
console.log(minSemestersOptimal(3, [[1,2],[2,3],[3,1]])); // -1

Line Notes

const graph = Array.from({length: n + 1}, () => [])Initialize adjacency list

const indegree = Array(n + 1).fill(0)Indegree array for prerequisites

const queue = []Queue for BFS

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

let semester = 0, processed = 0Initialize counters

while (queue.length > 0)Process courses semester by semester

semester++Increment semester count

processed++Count courses taken

indegree[nei]--Decrease indegree of dependent courses

if (indegree[nei] === 0) queue.push(nei)Add newly available courses

⏱

Complexity

TimeO(n + m) where m is number of relations

SpaceO(n + m) for graph and indegree arrays

Each node and edge is processed once, with explicit cycle detection by counting processed nodes.

💡 This approach is the most robust and efficient for large inputs, detecting cycles early.

Interview Verdict: Accepted

This is the best practice solution to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the BFS-based Kahn's algorithm (Approach 2 or 3) as it is efficient and straightforward.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n!)	O(n)	Yes (deep recursion)	N/A	Mention only - never code
2. Topological Sort BFS (Kahn's Algorithm)	O(n + m)	O(n + m)	No	Yes (can reconstruct order)	Code this approach
3. Optimal BFS with Explicit Cycle Detection	O(n + m)	O(n + m)	No	Yes	Code this approach for robustness

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal solution, and prepare to explain your approach 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.Step 3: Explain why brute force is inefficient and introduce topological sort.Step 4: Implement the BFS-based Kahn's algorithm solution.Step 5: Discuss cycle detection and edge cases.Step 6: Test your code with sample inputs.

Time Allocation

Clarify: 5min → Approach: 5min → Code: 15min → Test: 5min. Total ~30min

What the Interviewer Tests

The interviewer tests your understanding of graph modeling, topological sorting, cycle detection, and ability to implement BFS level-by-level traversal.

Common Follow-ups

• What if you can only take k courses per semester? → Use BFS with limited queue size per semester.
• How to detect cycles efficiently? → Use processed courses count or DFS with recursion stack.

💡 These follow-ups test your ability to adapt the solution to constraints and detect cycles, common in graph problems.

🔍

Pattern Recognition

When to Use

1) Problem involves tasks with prerequisites; 2) Need minimum time/steps to complete all; 3) Tasks can be done in parallel if prerequisites met; 4) Detect if impossible due to cycles.

Signature Phrases

minimum number of semestersprerequisite coursescan take multiple courses in one semesterimpossible to finish

NOT This Pattern When

Problems that require longest path in DAG with weights or DP on DAG are different patterns.

Similar Problems

Course Schedule - checks if all courses can be finished (cycle detection)Course Schedule II - returns one valid order of coursesMinimum Number of Semesters to Finish All Courses - similar problem with course limits

Practice

1. You need to construct a matrix where each row and column must satisfy a set of ordering constraints given as pairs (a before b). Which algorithmic approach best guarantees a valid construction if one exists?

easy

A. Greedy approach that places elements in the earliest available position without checking for cycles

B. Topological sort on the dependency graph to determine valid positions for each element

C. Dynamic programming to find the longest increasing subsequence of elements based on constraints

D. Divide and conquer by splitting constraints into smaller independent sets and merging results

Solution

1. Step 1: Understand the problem as ordering with dependencies

   The problem requires respecting partial order constraints, which naturally maps to a directed graph where edges represent "before" relations.

2. Step 2: Identify the algorithm that handles partial orders and detects cycles

   Topological sort is the standard algorithm to order nodes in a DAG respecting dependencies and detect cycles if no valid order exists.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort guarantees a valid order or detects impossibility [OK]

Hint: Partial order constraints -> topological sort [OK]

Common Mistakes:

• Assuming greedy placement always works
• Confusing with DP longest subsequence
• Ignoring cycle detection

2. Given the following code implementing Kahn's Algorithm for course scheduling, what is the final output when calling findOrder(4, [[1,0],[2,0],[3,1],[3,2]])?

easy

A. [0, 1, 2, 3]

B. []

C. [3, 1, 2, 0]

D. [0, 2, 1, 3]

Solution

1. Step 1: Initialize in-degree and queue

   In-degree: [0,1,1,2]; queue starts with [0] since only course 0 has in-degree 0.

2. Step 2: Process queue and update order

   Pop 0 -> order=[0]; neighbors 1 and 2 in-degree decremented to 0 -> queue=[1,2]; pop 1 -> order=[0,1]; neighbor 3 in-degree decremented to 1; pop 2 -> order=[0,1,2]; neighbor 3 in-degree decremented to 0 -> queue=[3]; pop 3 -> order=[0,1,2,3].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Order respects prerequisites and includes all courses [OK]

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

Common Mistakes:

• Mixing order of nodes popped from queue
• Forgetting to decrement in-degree
• Returning empty list incorrectly

3. Consider the following code snippet implementing the optimal solution for the longest path with different adjacent characters problem. Given n = 3, edges = [[0,1],[1,2]], and s = "aba", what is the final returned value?

easy

A. -1

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace topological order and dp array

   Topological order is [0,1,2]. Initialize dp = [1,1,1]. - For node 0: neighbor 1, s[1] = 'b' != s[0] = 'a', dp[1] = max(1, 1+1) = 2. - For node 1: neighbor 2, s[2] = 'a' != s[1] = 'b', dp[2] = max(1, 2+1) = 3.

2. Step 2: Compute final answer

   Maximum dp value is 3, which is returned.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp array ends as [1, 2, 3], max is 3 [OK]

Hint: Check dp updates along topo order carefully [OK]

Common Mistakes:

• Returning dp[node] instead of max(dp)
• Ignoring character difference condition
• Miscomputing topological order

4. Consider the following buggy code snippet for topological sort positions. Which line contains the subtle bug that can cause incorrect matrix construction?

medium

A. Line where graph[u].append(v) is called

B. Line where queue is initialized with nodes of zero in-degree

C. Line where pos[node] is assigned idx

D. Line where in_degree[u] is incremented instead of in_degree[v]

Solution

1. Step 1: Identify how in-degree is updated

   In-degree should count incoming edges; incrementing in_degree[u] is incorrect because u is the source, not the target.

2. Step 2: Understand impact of bug

   Incorrect in-degree counts cause wrong zero in-degree nodes, breaking topological order and matrix correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct in-degree update is critical for cycle detection and ordering [OK]

Hint: In-degree counts incoming edges, not outgoing [OK]

Common Mistakes:

• Mixing source and target when updating in-degree
• Assuming graph edges are undirected

5. Suppose the course prerequisites can form multiple disconnected subgraphs and some courses have no prerequisites. How should Kahn's Algorithm be modified to return a valid order including all courses?

hard

A. Initialize the queue with all nodes having zero in-degree, including those in disconnected components.

B. Use backtracking to try all permutations since BFS cannot handle disconnected graphs.

C. Run DFS from each node separately and concatenate results without cycle checks.

D. Start BFS from any arbitrary node and ignore disconnected components.

Solution

1. Step 1: Identify disconnected components

   Courses with no prerequisites form disconnected subgraphs with zero in-degree nodes.

2. Step 2: Initialize queue with all zero in-degree nodes

   Queue must include all such nodes to process all components and produce a full valid order.

3. Step 3: Process BFS as usual

   Processing all zero in-degree nodes ensures all courses are included in the order.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Queue initialization with all zero in-degree nodes covers disconnected graphs [OK]

Hint: Queue must start with all zero in-degree nodes, not just one [OK]

Common Mistakes:

• Starting BFS from a single node only
• Ignoring disconnected components
• Skipping cycle detection in DFS