Course Schedule II LeetCode solution in JavaScript

1
/**
2
 * @param {number} numCourses
3
 * @param {number[][]} prerequisites
4
 * @return {number[]}
5
 */
6
var findOrder = function (numCourses, prerequisites) {
7
  let visiting = new Set();
8
  const visited = new Set();
9
  const adjList = new Map();
10
  const result = [];
11

12
  // Generate scaffold of adjacency list
13
  // initialized with no prereqs
14
  for (let i = 0; i < numCourses; i++) {
15
    adjList.set(i, []);
16
  }
17

18
  // Fill adjacency list with course prereqs
19
  // Key is the course
20
  // Value is any course prereqs
21
  for (const item of prerequisites) {
22
    const [course, prereq] = item;
23
    adjList.get(course).push(prereq);
24
  }
25

26
  const dfs = (node) => {
27
    // We've already traversed down this path before
28
    // and determined that it isn't cyclical
29
    if (visited.has(node)) return true;
30

31
    // Visiting keeps track of what we've seen
32
    // during this current traversal and determines
33
    // if we have a cycle.
34
    if (visiting.has(node)) return false;
35

36
    // Mark this node as part of the current traversal
37
    visiting.add(node);
38

39
    // Get all adjacent nodes to traverse
40
    // traverse them in a loop looking for cycles
41
    const children = adjList.get(node);
42
    for (const child of children) {
43
      if (!dfs(child)) return false;
44
    }
45

46
    // Ensures we don't re-traverse already traversed nodes since
47
    // we've already determined they contain no cycles.
48
    visited.add(node);
49

50
    // Add this node to the result stack to return at the end
51
    result.push(node);
52
    return true;
53
  };
54

55
  for (const node of adjList.keys()) {
56
    if (!dfs(node)) return [];
57
  }
58

59
  return result;
60
};