DevExCode

LeetCode 210: Course Schedule II Solution

Master LeetCode problem 210 (Course Schedule II), 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.

Problem Explanation

Explanation

To solve this problem, we can use a topological sorting algorithm known as Kahn's algorithm. The algorithm works by finding a valid course ordering by first identifying courses with no prerequisites, updating the prerequisites for other courses accordingly, and repeating the process until all courses are taken.

Here are the steps for the algorithm:

  1. Create an adjacency list to represent the graph where each course is a node and each prerequisite is an edge.
  2. Initialize an array indegree to store the indegree of each course (number of prerequisites).
  3. Initialize a queue queue to store courses with no prerequisites.
  4. Add courses with an indegree of 0 to the queue.
  5. While the queue is not empty, remove a course from the queue and add it to the result list.
  6. For each course removed from the queue, decrease the indegree of its adjacent courses.
  7. If any course has an indegree of 0 after decreasing, add it to the queue.
  8. Repeat steps 5-7 until the queue is empty.
  9. If the result list size is equal to the total number of courses, return the result list. Otherwise, return an empty array.

The time complexity of this algorithm is O(V + E), where V is the number of courses and E is the number of prerequisites. The space complexity is O(V + E) for the adjacency list, indegree array, and queue.

Solution Code

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        int[] indegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for (int[] prerequisite : prerequisites) {
            adjList.get(prerequisite[1]).add(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result.add(course);
            
            for (int nextCourse : adjList.get(course)) {
                indegree[nextCourse]--;
                if (indegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }
        
        if (result.size() == numCourses) {
            return result.stream().mapToInt(Integer::valueOf).toArray();
        } else {
            return new int[0];
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 210 (Course Schedule II)?

This page provides optimized solutions for LeetCode problem 210 (Course Schedule II) 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 210 (Course Schedule II)?

The time complexity for LeetCode 210 (Course Schedule II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 210 on DevExCode?

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

Back to LeetCode Solutions