// Runtime: 3 ms, faster than 96.33% of Java online submissions for Course Schedule II.
// Memory Usage: 45.4 MB, less than 92.68% of Java online submissions for Course Schedule II.
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] dc = new int[numCourses];

        LinkedList<Integer>[] deps = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) deps[i] = new LinkedList<Integer>();

        for (int[] req: prerequisites) {
            deps[req[1]].add(req[0]);
            dc[req[0]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int node = 0; node < numCourses; node++)
            if (dc[node] == 0) q.add(node);

        int[] res = new int[numCourses];
        int rPos = 0;

        while (q.size() > 0) {
            int node = q.remove();
            for (int d: deps[node]) if (--dc[d] == 0) q.add(d);
            res[rPos++] = node;
        }

        if (rPos < numCourses) return new int[0];

        return res;
    }
}