LeetCode 1136: Parallel Courses Solution

Master LeetCode problem 1136 (Parallel Courses), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1136. Parallel Courses

Medium

Graph Topological Sort

Problem Explanation

Explanation:

To solve this problem, we can model the courses and their dependencies as a directed graph. We need to find the minimum number of semesters required to take all the courses such that prerequisites are satisfied. This problem can be solved using a topological sort approach.

Create a directed graph where each course is a node and the prerequisites are edges between nodes.
Calculate the in-degree of each node representing the number of prerequisites for that course.
Initialize a queue with all the courses that have no prerequisites.
While the queue is not empty, remove a course from the queue, decrement the in-degree of its adjacent nodes, and add any new courses with no prerequisites to the queue.
Keep track of the number of semesters passed and the number of courses taken.
The final answer will be the number of semesters needed to complete all courses.

Solution Code

class Solution {
    public int minimumSemesters(int N, int[][] relations) {
        List<Integer>[] graph = new ArrayList[N + 1];
        int[] inDegree = new int[N + 1];
        
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] relation : relations) {
            int from = relation[0];
            int to = relation[1];
            
            graph[from].add(to);
            inDegree[to]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        
        int semesters = 0;
        int coursesTaken = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            coursesTaken += size;
            semesters++;
            
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                
                for (int nextCourse : graph[course]) {
                    inDegree[nextCourse]--;
                    if (inDegree[nextCourse] == 0) {
                        queue.add(nextCourse);
                    }
                }
            }
        }
        
        return coursesTaken == N ? semesters : -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1136 (Parallel Courses)?

This page provides optimized solutions for LeetCode problem 1136 (Parallel Courses) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1136 (Parallel Courses)?

The time complexity for LeetCode 1136 (Parallel Courses) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1136 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1136 in Java, C++, or Python.

Back to LeetCode Solutions