Untitled

 avatar
unknown
java
5 months ago
1.8 kB
2
Indexable
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> adjMap = new HashMap<>();

        // Set each preqreq for each coruse to be 0
        // HashMap<Integer, Integer> numPreqs = new HashMap<>();
        int[] numPreqs = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            // numPreqs.put(i, 0);
            adjMap.put(i, new ArrayList<Integer>());
        }
        
        // Set up adjMap. For each child, list its preqreqs
        // Child means that there are preqreqs
        // Parent means that it is a preqreq
        for (int i = 0; i < prerequisites.length; i++) {
            int childClass = prerequisites[i][0];
            int parentClass = prerequisites[i][1];
            numPreqs[childClass]++;
            adjMap.get(parentClass).add(childClass);
        }


        Queue<Integer> queue = new LinkedList<>();
        // See which classes have no preqreqs
        for (int i = 0; i < numCourses; i++) {
            if (numPreqs[i] == 0) {
                queue.add(i);
            }
        }

        int[] order = new int[numCourses];
        int index = 0;
        while (!queue.isEmpty()) {
            int courseNumber = queue.remove();
            order[index] = courseNumber;
            index++;

            // Everytime we look at a course we should remove it from the list of it's parents preqreqs
            for (int childClass : adjMap.get(courseNumber)) {
                numPreqs[childClass]--;
                if (numPreqs[childClass] == 0) {
                    queue.add(childClass);
                }         
            }
        }

        if (index == numCourses) {
            return order;
        } else {
            return new int[0];
        }
    }
}
Editor is loading...
Leave a Comment