Problem: Course Schedule (Cycle Detection)

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Return true if you can finish all courses. Otherwise, return false.

Approach: Kahn's Algorithm (BFS)

This is a classic Cycle Detection problem in a directed graph. If there's a cycle, you can never complete the courses.

1. Build Graph: Create an adjacency list and calculate the in-degree (number of prerequisites) for every course.
2. Queue: Add all courses with 0 in-degree to a queue (courses you can take immediately).
3. Process:
   • Pop a course from the queue.
   • Increment a count of completed courses.
   • For each of its neighbors (courses that depend on this one):
     • Decrement their in-degree.
     • If in-degree becomes 0, add to queue.
4. Result: If count == numCourses, return true.

Java Implementation

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    
    for (int[] pre : prerequisites) {
        adj.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);
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int curr = queue.poll();
        count++;
        for (int next : adj.get(curr)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    
    return count == numCourses;
}

Complexity Analysis

• Time Complexity: $O(V + E)$ where $V$ is courses and $E$ is prerequisites.
• Space Complexity: $O(V + E)$ for the adjacency list.

Interview Tips

• Mention that this is "Cycle Detection using BFS."
• You can also solve this using DFS by checking for "Back Edges" in the recursion stack.