166. Course Schedule II

Start with courses that have no prerequisites. Remove them and reduce in-degree of dependent courses. Repeat until all courses are processed or a cycle is detected.

Approach

1. Build adjacency list and in-degree array.
2. Enqueue all nodes with in-degree 0.
3. BFS: dequeue, add to order, decrement neighbors' in-degree.
4. If order length == numCourses, return it; else cycle exists.

Complexity

• Time: O(V + E)
• Space: O(V + E)

import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];

        for (int[] pre : prerequisites) {
            graph.computeIfAbsent(pre[1], k -> new ArrayList<>()).add(pre[0]);
            inDegree[pre[0]]++;
        }

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

        int[] order = new int[numCourses];
        int idx = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order[idx++] = node;
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) queue.add(neighbor);
            }
        }

        return idx == numCourses ? order : new int[0];
    }
}