|
1 | 1 | class Solution { |
2 | 2 | public int[] findOrder(int numCourses, int[][] prerequisites) { |
3 | | - Map<Integer, List<Integer>> map = new HashMap<>(); |
4 | | - int[] prereqCount = new int[numCourses]; |
| 3 | + Map<Integer, List<Integer>> prerequisiteToCourseDependency = new HashMap<>(); |
| 4 | + int[] prerequisiteCount = new int[numCourses]; |
5 | 5 | for (int[] prerequisite : prerequisites) { |
6 | | - prereqCount[prerequisite[0]]++; |
7 | | - map.computeIfAbsent(prerequisite[1], k -> new ArrayList<>()).add(prerequisite[0]); |
| 6 | + prerequisiteToCourseDependency.computeIfAbsent(prerequisite[1], k -> new ArrayList<>()) |
| 7 | + .add(prerequisite[0]); |
| 8 | + prerequisiteCount[prerequisite[0]]++; |
8 | 9 | } |
9 | 10 | Queue<Integer> queue = new LinkedList<>(); |
10 | 11 | for (int i = 0; i < numCourses; i++) { |
11 | | - if (prereqCount[i] == 0) { |
| 12 | + if (prerequisiteCount[i] == 0) { |
12 | 13 | queue.add(i); |
13 | 14 | } |
14 | 15 | } |
15 | | - int[] ans = new int[numCourses]; |
16 | | - int idx = 0; |
| 16 | + int[] courseOrder = new int[numCourses]; |
| 17 | + int courseOrderIdx = 0; |
17 | 18 | while (!queue.isEmpty()) { |
18 | | - int removed = queue.remove(); |
19 | | - for (Integer dependentCourse : map.getOrDefault(removed, new ArrayList<>())) { |
20 | | - prereqCount[dependentCourse]--; |
21 | | - if (prereqCount[dependentCourse] == 0) { |
| 19 | + int course = queue.remove(); |
| 20 | + courseOrder[courseOrderIdx++] = course; |
| 21 | + for (Integer dependentCourse : prerequisiteToCourseDependency.getOrDefault(course, new ArrayList<>())) { |
| 22 | + prerequisiteCount[dependentCourse]--; |
| 23 | + if (prerequisiteCount[dependentCourse] == 0) { |
22 | 24 | queue.add(dependentCourse); |
23 | 25 | } |
24 | 26 | } |
25 | | - ans[idx++] = removed; |
26 | 27 | } |
27 | | - return idx == numCourses ? ans : new int[]{}; |
| 28 | + return courseOrderIdx == numCourses ? courseOrder : new int[]{}; |
28 | 29 | } |
29 | 30 | } |
0 commit comments