Leetcode: Course Schedule

 This question is asked at Amazon, Facebook, Intuit, Karat, and Microsoft, as well as TikTok. There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1 and you are given an array prerequesites that you must take course b1 first before ai, in the pair [a1, b1]. We return true if we can finish all the courses, otherwise, we have to return false. 

Here are some examples: 

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: There are a total of 2 courses to take. 

To take course 1 you should have finished course 0. So it is possible.

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: There are a total of 2 courses to take. 

To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Now let's approach solving the problem. 

The output either has to be true or fale if we can complete all the courses before their prerequisites. So as a result, we need to detect a cycle in a graph. 

I'm going to explain topological sort here, where we willl use an indegree, the number of edges poinitng into a node. 

Let's first go over Topological Sort, where we discuss what is TopSort, when it's used and how to find a topological ordering. 

Many real-world situations can be modelled as a graph. Some simple examples are schools, class prerequisites, program dependencies, etc. 

Suppose you're a university student and you want to take class H, but before you take class H, you need to take D and E but before that you must have taken A and B without any prerequisites. 

A program CANNOT BE BUILT UNLESS ALL OF ITS DEPENDENCIES ARE BUILT. TopSort comes unto play to find a valid ordering of the programs. 

We can align all nodes in the line and have all the edges pointed to the right and we can sort them in O(V + E) time! There cannot be a ordering if there is a cyclical ordering, so any graph with a directed cycle is forbidden. Directed Acyclic Graphs (DAG) have valid topological orderings. How do you verify that graph does not contain directed cycle? We can use Tarjan's algorithm. Since Trees don't have any cycles, every tree as a result has a topological ordering. 

Pick an unvisited node, do a DFS exploring unvisitive notes, and add the current node to the ordering in reverse order. First step is to pick an unvisited node. Do a DFS exploring where we can, until there is no other node, then append that node to our final stack. 

Now if there are 3 arrows goinginto a node, it has degree 3, with one arraw going in the node, it's a degree one, etc. 

Now we want to walk through all of the indegrees and we'll havge a queue and keep track of a variable called count, keeping track of all the nodes that we popped from the node.

1. Keep an adjacency list representation of the graph

2. Keep all of the nodes. 

BFS uses indegrees inside of the node. We try to find a node with a 0 indegree, and if this doesn't work we set indegree to -1 to prevent from visiting the node again and reduce the indegrees of its neighbors. 

Keep track of the indegrees of each one of the nodes. We push everyt single node with an indegree into the queue, and start our standard BFS. We decrement each indegree by one. It's really similar to braking the connection to the node and eventually we want to see that all nodes have no connections and count equals the total number of nodes. 

And here's the solution written out: 

class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        //course relation graph

        int[][] matrix = new int[numCourses][numCourses];

        //number of prerequisites

        int[] indegree = new int[numCourses];

        //add to the matrix the courses and the number of prereqs

        for(int i = 0; i < prerequisites.length; i++) {

            int ready = prerequisites[i][0];

            int pre = prerequisites[i][1];

            if(matrix[pre][ready] == 0) indegree[ready]++;

            matrix[pre][ready] = 1;

        }

        int count = 0;

        Queue<Integer> queue = new LinkedList();

        //offer all the courses with no prereqs, these are the roots. 

        for(int i = 0; i < indegree.length; i++) {

            if(indegree[i] == 0) queue.offer(i); 

        }

       //go through queue

        while(!queue.isEmpty()) {

            int course = queue.poll(); 

            //add the count to keep track of the number of courses with no prereqs.

            count++;

            //see the course connections, and add these as the root

            for(int i = 0; i < numCourses; i++) {

                if(matrix[course][i] != 0) {

                    indegree[i]--;

                    if(indegree[i] == 0) queue.offer(i);

                }

            }

        }

       //this checks to see if there is a proper cycle. 

        return count == numCourses;

    }

}