For today’s Leetcode July Challenge we have the opportunity to implement a textbook algorithm. The problem, Course Schedule II presents us with a total number of courses where each course is assumed to be numbered from 0 to n-1 and a list of course-prerequisite pairs in the form [course number, prerequisite number]. Given this, we are asked to return a valid ordering of all courses, if one exists, such that no course is taken before its prerequisite. If you’re not already familiar with the setup it can take a moment to notice, but this is actually a graph problem wherein each course is a vertex and each prerequisite pair is a directed edge from the prerequisite to the course vertex. And the valid ordering, one where every edge in the graph, uv, from vertex u to vertex v precedes the vertex v, is called topological sort. Topological sorting is an incredibly important algorithm across a variety of domains from the macro and practical, as in our problem, to the abstract and low-level, as in chip instruction scheduling and symbolic logic processing. I’ll use a variation of the well-known Kahn’s algorithm for this problem, which has an asymptotic complexity O(Vertices+Edges).

Our implementation of this algorithm has a vew basic steps. First things first, we’ll translate our inputs to an adjacency list graph representation and make a list of each nodes indegree–the number of graph edges directed towards that node. Next, we push all the root nodes–nodes with an indegree of 0–to a queue or stack. One really interesting thing about this algorithm, which I’ll show, is that we can use a queue or a stack interchangably to produce distinct topological sorts if they exist. Finally we search the graph by selecting a root node from the stack/queue putting it in our schedule, then removing it from the graph, which here means to decrement the indegree of its adjacent nodes, and push any of its adjacent nodes that are now root nodes to the stack/queue. Once the search has been exhausted, if all the courses are in the schedule, we can return the schedule as a topological sort. If there are fewer courses in the schedule than the total number of courses, it indicates that there is a cycle in the graph and thus a topological sort isn’t possible.

I’ll present two versions of the algorithm below with the only difference being that one uses a stack and the other uses a queue, just to show how neat that is. I hope you enjoyed my ramblings about this important algorithm.

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
   // build the graph representation
   vector<vector<int>> adjGraph(numCourses);
   vector<int> indegree(numCourses);
   for(auto course : prerequisites) {
	  adjGraph[course[1]].push_back(course[0]);
	  indegree[course[0]]++;
   }
   // push all root nodes to the queue/stack.
   queue<int> q;
   for(int i=0;i<indegree.size();i++) {
	  if(indegree[i] == 0) {
		 q.push(i);
	  }
   }
   // search the graph
   vector<int> schedule;
   while(!q.empty()) {
	  int course = q.front(); q.pop();
	  schedule.push_back(course);
	  for(auto adj : adjGraph[course]) {
		 indegree[adj]--;
		 if(indegree[adj] == 0) {
			q.push(adj);
		 }
	  }
   }
   if(schedule.size() == numCourses) return schedule;
   return {};
}

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
   // build the graph representation
   vector<vector<int>> adjGraph(numCourses);
   vector<int> indegree(numCourses);
   for(auto course : prerequisites) {
	  adjGraph[course[1]].push_back(course[0]);
	  indegree[course[0]]++;
   }
   // push all root nodes to the queue/stack.
   stack<int> s;
   for(int i=0;i<indegree.size();i++) {
	  if(indegree[i] == 0) {
		 s.push(i);
	  }
   }
   // search the graph
   vector<int> schedule;
   while(!s.empty()) {
	  int course = s.top(); s.pop();
	  schedule.push_back(course);
	  for(auto adj : adjGraph[course]) {
		 indegree[adj]--;
		 if(indegree[adj] == 0) {
			s.push(adj);
		 }
	  }
   }
   if(schedule.size() == numCourses) return schedule;
   return {};
}