Parallel Courses - Leetcode Solution

Problem Statement:

You are given an integer n which denotes the number of courses offered by a university labeled from 1 to n. Some courses may have prerequisites, which is shown in a pair of integers [a, b] where a is the prerequisite course for b.

For example, if [1, 2] is a pair of integers showing that course 1 is a prerequisite for course 2, it means that to take course 2, you have to first take course 1.

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are multiple correct answers, return any of them. If it is impossible to finish all courses, return an empty array.

Solution:

The problem can be represented as a graph problem. We will represent the prerequisites as edges between the graph nodes and then we can use a topological sort to find the valid path that satisfies all the prerequisites.

The basic idea for this algorithm is to first create an adjacency list of all the courses, where the prerequisite course points towards the course it is a prerequisite for (reversed order from the input array). We also create an array to store all the incoming edges for each course, which is a simple count of the number of times a prerequisite is required.

We create a queue and add the courses which don’t require prerequisites to be completed (i.e., those courses which have no incoming edges). This is the initial set of courses that can be completed.

We then follow the following steps:

1. Dequeue a course from the queue.
2. Check if this course leads to any other courses by checking its adjacency list.
3. For each course that the current course leads to, decrement the incoming edges count by one.
4. If this course leads to any other courses which have no incoming edges, add those courses to the queue as well.
5. Repeat steps 1-4 until the queue is empty.

After this algorithm finishes, we need to check if all courses have been completed or not.

Implementation:

We can use a hashmap to create the adjacency list. The key represents the course and the value is a list of all the courses that this course leads to.

To count incoming edges, simply loop over all of the prerequisites, where each prerequisite (b) adds an incoming edge count to the course (a), i.e., incomingEdges[b]++.

Code:

Here's the code that implements the above algorithm.

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] incomingEdges = new int[numCourses];
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        int[] result = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            adjList.put(i, new ArrayList<>());
        }

        for (int[] prereq : prerequisites) {
            incomingEdges[prereq[0]]++;
            adjList.get(prereq[1]).add(prereq[0]);
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < incomingEdges.length; i++) {
            if (incomingEdges[i] == 0) {
                queue.offer(i);
            }
        }

        int index = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[index++] = course;

            for (int c : adjList.get(course)) {
                incomingEdges[c]--;
                if(incomingEdges[c] == 0) {
                    queue.offer(c);
                }
            }
        }

        if (index != numCourses) {
            return new int[0];
        }

        return result;
    }
}

1