Very easy-to-understand solution in JavaScript with explaination


  • 0
    function canFinish(numCourses, prerequisites) {
      class Course {
        constructor() {                // If we had an instance of `Course` called X:
          this.numPrerequisites = 0;   // how much prerequisites X has
          this.isPrerequisiteFor = []; // how much courses have a prerequisite of X
          this.clear = false;          // whether X has been counted to `finished`
        }
      }
    
      // initialize
      const courses = [];
      for (let i = 0; i < numCourses; i++) courses[i] = new Course();
    
      prerequisites.forEach(([a, b]) => {
        courses[a].numPrerequisites++;
        courses[b].isPrerequisiteFor.push(a);
      });
    
      let finished = 0; // how much courses can be finished (clear=true)
      let prev = -1;    // trace the value of `finished` in previous iteration
    
      // terminate the loop if we cannot find out any new course able to be finished within one iteration
      while (finished > prev) {
        prev = finished;
    
        for (let i = 0; i < numCourses; i++) {
          if (courses[i].numPrerequisites === 0 && !courses[i].clear) {
            // courses[i] has no prerequisites or all of its prerequisites has been fulfilled
            // `clear=false` means we have to notify the courses which have prerequisite of course[i]
            courses[i].isPrerequisiteFor.forEach((j) => {
              // notify courses[j]
              courses[j].numPrerequisites--;
            });
            courses[i].clear = true;
            finished++;
          }
        }
      }
    
      return finished === numCourses;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.