210 Course Schedule II.js

// There are a total of n courses you have to take, labeled from 0 to n - 1.

// Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

// Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

// There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

// For example:

// 2, [[1,0]]
// There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

// 4, [[1,0],[2,0],[3,1],[3,2]]
// There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

// Note:
// The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

// click to show more hints.

// Hide Company Tags Facebook Zenefits
// Hide Tags Depth-first Search Breadth-first Search Graph Topological Sort
// Hide Similar Problems (M) Course Schedule (H) Alien Dictionary (M) Minimum Height Trees

// 160ms

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
  var courseWithOtherCoursesDependOn = {};
  var courseDependsOnOtherCourses = {};

  prerequisites.forEach(prerequisite => {
    var prereqCourse = prerequisite[1];
    var courseToTake = prerequisite[0];

    courseWithOtherCoursesDependOn[prereqCourse] =
      courseWithOtherCoursesDependOn[prereqCourse] || new Set();
    courseWithOtherCoursesDependOn[prereqCourse].add(courseToTake);

    courseDependsOnOtherCourses[prereqCourse] =
      courseDependsOnOtherCourses[prereqCourse] || new Set();
    courseDependsOnOtherCourses[courseToTake] =
      courseDependsOnOtherCourses[courseToTake] || new Set();
    courseDependsOnOtherCourses[courseToTake].add(prereqCourse);
  });

  var courseWithNoDependencies = [];

  for (var i in courseDependsOnOtherCourses) {
    if (courseDependsOnOtherCourses[i].size === 0) {
      courseWithNoDependencies.push(i);
    }
  }

  // pretty much the same as Course Schedule I. Just need to add those non root
  var courseOrders = [];
  var hasCourseOrders = {};

  while (courseWithNoDependencies.length > 0) {
    var rootCourse = courseWithNoDependencies.shift();

    courseOrders.push(parseInt(rootCourse));
    hasCourseOrders[parseInt(rootCourse)] = true;

    if (courseWithOtherCoursesDependOn[rootCourse]) {
      courseWithOtherCoursesDependOn[rootCourse].forEach(childCourse => {
        courseDependsOnOtherCourses[childCourse].delete(parseInt(rootCourse));

        if (courseDependsOnOtherCourses[childCourse].size === 0) {
          courseWithNoDependencies.push(childCourse + "");
        }
      });
    }
  }

  for (i in courseDependsOnOtherCourses) {
    if (courseDependsOnOtherCourses[i].size !== 0) {
      return [];
    }
  }

  if (courseOrders.length < numCourses) {
    for (i = 0; i < numCourses; i++) {
      if (!hasCourseOrders[i]) {
        courseOrders.push(i);
      }
    }
  }

  return courseOrders;
};

console.log(findOrder(3, [[1, 0]]));