Course Schedule II

JavaView on GFG

Time: O(V+E)

Space: O(V+E)

Intuition

Return a valid course order (topological sort). If cycle exists, return empty array.

Algorithm

1Kahn's algorithm: build adjacency list, compute in-degrees.
2Queue all nodes with in-degree 0. Process queue: add to order, decrement neighbors' in-degrees, add neighbors with in-degree 0.
3If order.size == n, return order. Else return [].

Common Pitfalls

•Return any valid topological order, not a specific one. Empty array signals impossible (cycle).

Course Schedule II.java

Java

// Approach: Topological sort (BFS Kahn's). Collect nodes in processing order for the valid course sequence.
// Time: O(V+E) Space: O(V+E)
import java.util.*;

class Solution {
    public ArrayList<Integer> findOrder(int n, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> ansList = new ArrayList<>();

        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());

        for (int[] prerequisite : prerequisites) {
            int u = prerequisite[1];
            int v = prerequisite[0];
            graph.get(u).add(v);
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i])
                topoSort(graph, i, visited, stack);
        }
        
        while (!stack.isEmpty())
            ansList.add(stack.pop());

        return ansList;
    }

    public void topoSort(List<List<Integer>> graph, int i, boolean[] visited, Stack<Integer> stack) {
        visited[i] = true;

        for (int nei : graph.get(i)) {
            if (!visited[nei])
                topoSort(graph, nei, visited, stack);
        }
        stack.push(i);
    }
}

Was this solution helpful?