210. Course Schedule II

// LeetCode URL: https://leetcode.com/problems/course-schedule-ii/
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Using DFS
 *
 * Time Complexity: O(Vertices + Edges) = O(N + P).
 *
 * Space Complexity: O(Vertices + Edges) = O(N + P).
 *
 * In worst case (in DAG) P = N * (N - 1) / 2. Thus worst case complexity:
 * O(N^2). Refer: https://stackoverflow.com/a/11699123
 *
 * N = Number of Courses or Number of vertices. P = Number of prerequisites or
 * Number of edges.
 */
class Solution1 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) {
            return new int[0];
        }

        int[] result = new int[numCourses];

        if (numCourses == 1) {
            return result;
        }

        HashMap<Integer, HashSet<Integer>> graph = buildGraph(prerequisites, numCourses);
        HashSet<Integer> visited = new HashSet<>();
        HashSet<Integer> visiting = new HashSet<>();
        Stack<Integer> order = new Stack<>();

        for (int i = 0; i < numCourses; i++) {
            if (!visited.contains(i) && hasCycle(graph, i, visited, visiting, order)) {
                return new int[0];
            }
        }

        int i = 0;
        while (!order.isEmpty()) {
            result[i] = order.pop();
            i++;
        }

        return result;
    }

    private HashMap<Integer, HashSet<Integer>> buildGraph(int[][] prerequisites, int numCourses) {
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new HashSet<>());
        }
        if (prerequisites == null || prerequisites.length == 0) {
            return graph;
        }

        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
        }
        return graph;
    }

    private boolean hasCycle(HashMap<Integer, HashSet<Integer>> graph, int node, HashSet<Integer> visited,
            HashSet<Integer> visiting, Stack<Integer> order) {
        if (visited.contains(node)) {
            return false;
        }
        if (visiting.contains(node)) {
            return true;
        }

        visiting.add(node);

        for (int n : graph.get(node)) {
            if (!visited.contains(n) && hasCycle(graph, n, visited, visiting, order)) {
                return true;
            }
        }

        visiting.remove(node);
        visited.add(node);
        order.push(node);
        return false;
    }
}

/**
 * Using BFS
 *
 * Time Complexity: O(Vertices + Edges) = O(N + P).
 *
 * Space Complexity: O(Vertices + Edges) = O(N + P).
 *
 * In worst case (in DAG) P = N * (N - 1) / 2. Thus worst case complexity:
 * O(N^2). Refer: https://stackoverflow.com/a/11699123
 *
 * N = Number of Courses or Number of vertices. P = Number of prerequisites or
 * Number of edges.
 */
class Solution2 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) {
            return new int[0];
        }

        int[] result = new int[numCourses];

        if (numCourses == 1) {
            return result;
        }

        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];
        buildGraph(numCourses, prerequisites, graph, inDegree);

        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 course = queue.poll();
            result[count] = course;
            count++;
            for (int n : graph.get(course)) {
                inDegree[n]--;
                if (inDegree[n] == 0) {
                    queue.offer(n);
                }
            }
        }

        return count == numCourses ? result : new int[0];
    }

    private void buildGraph(int numCourses, int[][] prerequisites, HashMap<Integer, HashSet<Integer>> graph,
            int[] inDegree) {
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new HashSet<>());
        }
        if (prerequisites == null || prerequisites.length == 0) {
            return;
        }
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }
    }
}