algoadvance

Leetcode 210. Course Schedule II

Problem Statement

You are given a total of numCourses courses labeled from 0 to numCourses-1. You are also given an array of prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i before course a_i.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Constraints:

Clarifying Questions

  1. Does the number of courses (numCourses) always guarantee there will be a solution?
    • No, there might be no way to finish all courses due to cyclic dependencies.
  2. If there are multiple valid orderings of courses, is it acceptable to return any of them?
    • Yes, any valid ordering is acceptable.
  3. What should be returned if it is impossible to complete all the courses?
    • Return an empty array if it is impossible to finish all courses.

Strategy

This problem is a classic application of topological sorting for Directed Acyclic Graphs (DAG). Here is the overall strategy to be implemented:

  1. Build Graph Representation:
    • Use an adjacency list to represent the graph.
    • Maintain an array to capture in-degrees (number of incoming edges) for each course.
  2. Initialize Zero In-Degree Courses:
    • Use a queue to track nodes with in-degree zero (i.e., no prerequisites).
  3. Process the Graph:
    • Repeatedly dequeue courses from the front of the queue and add to the course ordering.
    • For each dequeued course, reduce the in-degree of its connected courses.
    • If the in-degree of any course becomes zero, enqueue it.
  4. Check for Cycles:
    • If all courses are processed, return the ordering.
    • If some courses remain unprocessed (in-degrees are not zero), there’s a cycle, hence return an empty array.

Code Implementation

import java.util.*;

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Step 1: Initialize data structures  
        List<List<Integer>> adjList = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // Step 2: Build the graph
        for (int[] prereq : prerequisites) {
            int dest = prereq[0];
            int src = prereq[1];
            adjList.get(src).add(dest);
            inDegree[dest]++;
        }

        // Step 3: Queue of all courses with no prerequisites (in-degree 0)
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        // Step 4: Process the nodes
        int[] order = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            int currentCourse = queue.poll();
            order[index++] = currentCourse;

            // Reduce the in-degree of neighboring nodes
            for (int neighbor : adjList.get(currentCourse)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // Step 5: Check if all nodes were processed
        return index == numCourses ? order : new int[0];
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.findOrder(4, new int[][]// use example above
        System.out.println(Arrays.toString(sol.findOrder(2, new int[][]// use example above
        System.out.println(Arrays.toString(sol.findOrder(2, new int[][]// use example above
    }
}

Time Complexity

This approach ensures efficient processing and correctly handles the detection of cycles in the graph.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI