Course Prerequisites

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Description

Here's a classic challenge that comes up in real-life interviews surprisingly often. Interviewers like it as a way to assess your ability to find the right data structure for a non-obvious and non-trivial use case.

The prompt is as follows: you're a university student currently trying to plan their schedule for the following semester. There is n number of courses that you'll need to take to stay on track for graduation.

Of the n courses, several have prerequisite courses that you'll need to take beforehand. This requirement is defined using an array with two elements. A prerequisite pair in the form [course, prerequisite] such as [4, 3] means that you need to take course 3 before course 4.

n = 3
preReqs = [[1, 0], [2, 1]]
// You need to take course 0 before 1, and 1 before 2, 
// but that is an appropriate order.
// Running areAllCoursesPossible(n, preReqs) would return true.

However, sometimes the prerequisite pairings are not possible-- this will prevent you from staying on track! As an example, if we add an additional prerequisite requirement that you need to finish 2 before 0, it wouldn't work:

n = 3
preReqs = [[1, 0], [2, 1], [0, 2]]
// This is impossible because you can't finish 2 before 0,
// since you need to finish 1 before 2, and 0 before 1.

In the above, an order of 0 -> 1 -> 2 or 2 -> 1 -> 0 would not fulfill the requirements, so areAllCoursesPossible(n, preReqs) would return false.

Given n and a list of prerequisite pairs, can you write a method to determine if it is possible to take all the courses? Hint: what are the conditions under which a prerequisite setup is impossible?

Constraints

Number of possible courses <= 100000
Number of prerequisites <= 100000
The prerequisites array will always contain the value >= 0
Expected time complexity : O(V+E) , where V are the courses and E are the prerequisites
Expected space complexity : O(V)

```js
class CourseSchedule {
  areAllCoursesPossible(numCourses, prerequisites) {
    // implement this method
    return true;
  };

  dfs(courseIdx, onThePath) {
    // might be helpful
  };
}
```
```java
public class CourseSchedule {
  public boolean areAllCoursesPossible(int numCourses, int[][] prerequisites) {
    // implement this method
    return true;
  }
  
  public void dfs(int courseIdx, boolean[] onThePath) {
    // might be helpful
  }
  
  public static void main(String[] args) {
    // Driver code here
  }
}
```
```javascript
class CourseSchedule {
  areAllCoursesPossible(numCourses, prerequisites) {
    // implement this method
    return true;
  }
  
  dfs(courseIdx, onThePath) {
    // might be helpful
  }
  
  // Driver code here
}
```
```python
class CourseSchedule:
  def are_all_courses_possible(self, num_courses, prerequisites):
    # implement this method
    return True
  
  def dfs(self, course_idx, on_the_path):
    # might be helpful
    pass
  
  if __name__ == "__main__":
    # Driver code here
    pass
```
```cpp
class CourseSchedule {
public:
  bool areAllCoursesPossible(int numCourses, vector<vector<int>>& prerequisites) {
    // implement this method
    return true;
  }
  
  void dfs(int courseIdx, vector<bool>& onThePath) {
    // might be helpful
  }
};

int main() {
  // Driver code here
}
```
```csharp
public class CourseSchedule {
  public static bool AreAllCoursesPossible(int numCourses, int[][] prerequisites) {
    // implement this method
    return true;
  }
  
  public static void Dfs(int courseIdx, bool[] onThePath) {
    // might be helpful
  }

  static void Main(string[] args) {
    // Driver code here
  }
}
```
```go
type CourseSchedule struct {
}

func (c *CourseSchedule) AreAllCoursesPossible(numCourses int, prerequisites [][]int) bool {
  // implement this method
  return true
}

func (c *CourseSchedule) DFS(courseIdx int, onThePath []bool) {
  // might be helpful
}

func main() {
  // Driver code here
}
```

CONTINUE WITH ALGODAILY PREMIUM

Keep going with the complete tutorial.

Unlock the remaining explanations and exercises, alongside the full learning library.

Explore Premium →

Open interactive view →