207. Course Schedule Leetcode Solution

Course Schedule Leetcode Problem :

There are a total of numCourses courses you have to take, labeled from 0 to numCourses – 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
  • Return true if you can finish all courses. Otherwise, return false.
jump game leetcode

Course Schedule Leetcode Solution :

Constraints :

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Example 1:

  • Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
  • Output: false

Intuition :

The intuition behind this approach is that if there is a cycle in the graph, there will be at least one node that cannot be visited since it will always have a nonzero indegree. On the other hand, if there are no cycles, all the nodes can be visited by starting from the nodes with no incoming edges and removing their outgoing edges one by one. If all the nodes are visited in the end, it means that it is possible to finish all the courses.

Approach :

The code aims to solve the problem of determining whether it is possible to finish all the given courses without any cyclic dependencies. It uses the topological sort algorithm, specifically Kahn’s algorithm, to solve this problem.

  1. Initialization:
    • Create an empty adjacency list to represent the directed graph. Each node in the graph represents a course, and the edges represent the prerequisites.
    • Create an array called indegree of size n (number of courses) and initialize all its elements to 0. The indegree array will keep track of the number of incoming edges to each course.
    • Create an empty ans vector to store the topological order of the courses.
  2. Building the Graph:
  • Iterate over the prerequisites vector, which contains pairs of courses indicating the prerequisites.
  • For each pair [a, b], add an edge in the adjacency list from b to a. This indicates that course b must be completed before course a.
  • Increment the indegree of course a by 1, as it has one more prerequisite.
  1. Performing Topological Sort using Kahn’s Algorithm:
    • Create an empty queue called q to store the nodes to visit.
    • Iterate over all the courses (0 to n-1) and enqueue the courses with an indegree of 0 into the queue. These courses have no prerequisites and can be started immediately.
    • While the queue is not empty, do the following:
      • Dequeue the front element from the queue and store it in a variable t.
      • Add t to the ans vector to keep track of the topological order.
      • For each neighbor x of t in the adjacency list:
        • Decrement the indegree of x by 1 since we are removing the prerequisite t.
        • If the indegree of x becomes 0, enqueue x into the queue. This means that all the prerequisites of course x have been completed.
  2. Checking the Result:
    • After the topological sort is complete, check if the size of the ans vector is equal to the total number of courses (n).
      • If they are equal, it means that all the courses can be finished without any cyclic dependencies. Return true.
      • If the sizes are different, it implies that there is a cycle in the graph, and it is not possible to complete all the courses. Return false.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription