Course Schedule I & II

Course Schedule II

Course Schedule I

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */

var findOrder = function (numCourses, prereqs) {
  if (numCourses === 0) {
    return [];
  }

  const n = prereqs.length;
  let adjList = new Array(numCourses);
  for (let i = 0; i < numCourses; i++) {
    adjList[i] = [];
  }

  for (let i = 0; i < prereqs.length; i++) {
    const [newClassId, newPrereqId] = prereqs[i];
    adjList[newPrereqId].push(newClassId);
  }

  // Count the indegress of the adjacency list
  let indegs = indegrees(adjList);

  // Get all the zero indegrees
  let zeroIndegree = indegs.reduce((acc, element, index) => {
    if (element === 0) acc.push(index);

    return acc;
  }, []);

  // Instantiate an array for topological sorting
  let sorted = [];
  // Topological sort via indegrees
  while (zeroIndegree.length > 0) {
    let nodeIndex = zeroIndegree.pop();
    sorted.push(nodeIndex);

    // Remove this node from the list and update all the nodes it pointed to. Meaning that they have one less prerequisite
    // and then if they now have 0 prereqs, add it to the queue
    for (let i = 0; i < adjList[nodeIndex].length; i++) {
      const neighbourId = adjList[nodeIndex][i];

      indegs[neighbourId]--;

      if (indegs[neighbourId] === 0) {
        zeroIndegree.push(neighbourId);
      }
    }
  }
  // Only return the topological sort if the number of nodes
  // in the sorted array is equal to the number of courses
  // otherwise that means there was some amount of nodes
  // without an indegree of 0 by the end of it (cyclic graph)

  // This commented line below solves Course Schedule II
  // return (sorted.length === numCourses) ? sorted : [];

  if (sorted.length === numCourses) {
    //
    return sorted;
  } else {
    return [];
  }
};

// Returns an array whos ith index contains the indegree for the ith class
function indegrees(adj) {
  let indegs = new Array(adj.length).fill(0);

  for (let i = 0; i < adj.length; i++) {
    const curList = adj[i];

    for (let j = 0; j < curList.length; j++) {
      indegs[curList[j]]++;
    }
  }

  return indegs;
}