Solution: Course Schedule II

Let's solve the Course Schedule II problem using the Topological Sort pattern.

We'll cover the following

Statement

Let’s assume that there are a total of nn courses labeled from 00 to n−1n-1. Some courses may have prerequisites. A list of prerequisites is specified such that if Prerequisitesi=a,bPrerequisites_i = {a, b}, you must take course bb before course aa.

Given the total number of courses nn and a list of the prerequisite pairs, return the course order a student should take to finish all of the courses. If there are multiple valid orderings of courses, then the return any one of them.

Note: There can be a course in the 00 to n−1n-1 range with no prerequisites.

Constraints:

Let nn be the number of courses.

  • 1≤n≤15001 \leq n \leq 1500
  • 0≤0 \leq prerequisites.length ≤1000\leq 1000
  • prerequisites[i].length ==2== 2
  • 0≤a, b<n0 \leq a, \space b < n
  • a≠ba \neq b
  • All the pairs [a, b][a, \space b] are distinct.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to use nested loops to iterate over the prerequisites list, find the dependency of one course on another, and store them in a separate array.

The time complexity of this naive approach is O(n2)O(n^2), where nn is the number of courses. However, the space complexity of this naive approach is O(n)O(n). Let’s see if we can use the topological sort pattern to reduce the time complexity of our solution.

Optimized approach using topological sort

This problem can be solved using the topological sort pattern. Topological sort is used to find a linear ordering of elements that depend on or prioritize each other. For example, if A depends on B or if B has priority over A, B is listed before A in topological order.

For this problem, we find the topological order of the given number of courses using the list of the courses’ prerequisites. Using the given list of prerequisites, we can build the graph representing the dependency of one course on another. To traverse a graph, we can use breadth-first search to find the courses’ order.

The vertices in the graph represent the courses, and the directed edge represents the dependency relationship. We get the order from the above example:

C6C_{6} → C4C_{4} → C1C_{1} → C5C_{5} → C2C_{2} → C3C_{3}

Another possible ordering of the above courses can be the following:

C6C_{6} → C4C_{4} → C5C_{5} → C1C_{1} → C2C_{2} → C3C_{3}

This order of graph vertices is known as a topological sorted order.

The basic idea behind the topological sort is to provide a partial ordering of the graph’s vertices so that if there’s an edge from UU to VV, then U≤VU ≤ V. This means UU comes before VV in the ordering. Let’s review some basic concepts that will help us understand topological sorting:

  1. Source: Any vertex with no incoming edge and only outgoing edges is called a source.

  2. Sink: Any vertex that has only incoming edges and no outgoing edge is called a sink.

So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks.

A topological ordering is possible only when the graph has no directed cycles, that is, if the graph is a Directed Acyclic Graph (DAG). No linear ordering among the vertices is possible if the graph has one or more cycles.

To find the topological sort of a graph, we can traverse the graph in a breadth-first Search (BFS) manner. We start with all the sources and save all of the sources to a sorted list in a stepwise fashion. We then remove all of the sources and their edges from the graph. After removing the edges, we have new sources, so we repeat the above process until all vertices are visited.

Here is how we will implement this algorithm:

  1. Initialization:

    • We store the graph in adjacency lists, where each parent vertex has a list containing all of its children. We do this using a hash map, where the key is the parent vertex number, and the value is a list containing the children’s vertex numbers.

    • To find the sources, we keep a hash map to count the in-degrees, which is the count of incoming vertices’ edges. Any vertex with a 00 in-degree is a source.

  2. Build the graph and find in-degrees of all vertices:

    • We build the graph from the input and populate the in-degrees hash map.

  3. Find all sources:

    • Our sources are all the vertices with 00 in degrees, and we store them in a queue.

  4. Sort:

    • For each source, we do the following:

      • Add it to the sorted list.

      • Retrieve all of its children from the graph.

      • Decrement the in-degree of each child by 11.

      • If a child’s in-degree becomes 00, add it to the source queue.

    • Repeat the first step until the source queue is’nt empty.

The following illustration might clarify this process.

Let’s look at the code for this solution below:

import java.util.*;
class CourseSchedule{
  
    public static List<Integer> findOrder(int n, int[][] prerequisites) {
        List<Integer> sortedOrder = new ArrayList<>();
        if (n <= 0)
            return sortedOrder;
        HashMap<Integer, Integer> inDegree = new HashMap<>();
        HashMap<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            inDegree.put(i, 0);
            graph.put(i, new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int parent = prerequisites[i][1], child = prerequisites[i][0];
            graph.get(parent).add(child);
            inDegree.put(child, inDegree.get(child) + 1);
        }
        Queue<Integer> sources = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0)
                sources.add(entry.getKey());
        }
        while (!sources.isEmpty()) {
            int vertex = sources.poll();
            sortedOrder.add(vertex);
            List<Integer> children = graph.get(vertex);
            for (int child : children) {
                inDegree.put(child, inDegree.get(child) - 1);
                if (inDegree.get(child) == 0)
                    sources.add(child);
            }
        }
        if (sortedOrder.size() != n)
            return new ArrayList<>();
        return sortedOrder;
    }
    public static void main(String[] args){
        // Driver code
        int[]n = {4, 5, 2, 4, 7};
        int[][][]prerequisites = {
        {{1, 0}, {2, 0}, {3, 1}, {3, 2}}, 
        {{1, 0}, {2, 0}, {3, 1},{4, 3}}, 
        {{1, 0}}, {{1, 0}, {2, 0}, {3, 1}, {3, 2}}, 
        {{1, 0}, {0, 3}, {0, 2}, {3, 2}, {2, 5}, {4, 5}, {5, 6}, {2, 4}}};
        for(int i=0; i<n.length; i++){
            System.out.print(i+1);
            System.out.println(".\tPrerequisites: "+Arrays.deepToString(prerequisites[i])+"\n\tTotal number of courses, n = "+n[i]);
            List<Integer> result = findOrder(n[i], prerequisites[i]);
            System.out.println("\tValid courses order: " + result);
            System.out.println(new String(new char[100]).replace('\0', '-')); 
        }
        
    }
}
Course Schedule II

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Make a graph by initializing the hash map with the vertices and their children.

  2. Keep the number of in-degrees of each of the vertex in the separate hash map.

  3. Find the source vertex.

  4. Add the source to the sorted list.

  5. Retrieve all the source children and add them to the queue.

  6. Decrement the in-degrees of the retrieved children.

  7. If the in-degree of the child vertex becomes equal to zero, add it to the sorted list.

  8. Repeat the process until the queue isn’t empty.

Time complexity

In step four, each vertex becomes a source only once, and each edge is accessed and removed once. Therefore, the above algorithm’s time complexity is O(v+e)O(v+e), where vv is the total number of vertices and ee is the total number of edges in the graph.

Space complexity

The space complexity is O(v+e)O(v+e) because we store all edges for each vertex in an adjacency list.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.