Untitled
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