Course Schedule II: the idea to remember.

The core insight

Queue courses with zero prerequisites remaining, then decrement dependent indegrees as courses are taken.

Why it works

Only a course whose prerequisites have all been processed enters the queue. If fewer than all courses are processed, a directed cycle remains.

The mistake to avoid

Prerequisite edges point from prerequisite to dependent. Count all processed courses to detect a cycle.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Visit prerequisites before adding a course and detect a cycle using the active recursion path.
public int[] findOrder(int numCourses, int[][] prerequisites) {
    Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>>();
    int[] indegree = new int[numCourses];
    int[] topologicalOrder = new int[numCourses];


    for (int i = 0; i < prerequisites.length; i++) {
        int post = prerequisites[i][0];
        int pre = prerequisites[i][1];
        List<Integer> lst = adjList.getOrDefault(
            pre,
            new ArrayList<Integer>()
        );
        lst.add(post);
        adjList.put(pre, lst);

        indegree[post] += 1;
    }

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

    int i = 0;
    while (!q.isEmpty()) {
        int node = q.remove();
        topologicalOrder[i++] = node;

        if (adjList.containsKey(node)) {
            for (Integer neighbor : adjList.get(node)) {
                indegree[neighbor]--;

                if (indegree[neighbor] == 0) {
                    q.add(neighbor);
                }
            }
        }
    }

    if (i == numCourses) {
        return topologicalOrder;
    }

    return new int[0];
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection