Problem Description

Question

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

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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 1:

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].

Example 2:

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].

Example 3:

Input: numCourses = 1, prerequisites = []Output: [0]

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
All the pairs [a_i, b_i] are distinct.

Solve it on LeetCode

Approaches

1. DFS-Based Topological Sorting

The problem of finding an order of courses to take based on prerequisites can be represented as finding a topological sort of a directed graph. Here, each course is a node, and each prerequisite relationship is a directed edge between two nodes.

Intuition:

Graph Representation: We represent our courses as nodes and prerequisites as directed edges between these nodes.
DFS for Cycle Detection and Ordering: Perform DFS to detect cycles in the graph and to help build the ordering of the courses. If we detect a cycle, it's impossible to complete all courses.
Topological Sort: As we exit the DFS for a node, it's added to the ordering stack/list, ensuring that prerequisites come first before the courses that depend on them.

Steps:

Construct a graph using adjacency list representation.
Use a visited list to track the visit status of nodes: unvisited, visiting, or visited.
Use a stack to assist in constructing the topological order.

Code:

Complexity Analysis

Time Complexity: O(V + E), where V is the number of courses and E is the number of prerequisite pairs.
Space Complexity: O(V + E) for the graph and recursion stack.

2. Kahn’s Algorithm (BFS-Based Topological Sorting)

Intuition:

In-Degree Calculation: Calculate the in-degree for each node (number of prerequisites for each course).
Queue Processing: Use a queue to process nodes with in-degree of 0 (no prerequisites).
Order Construction: Gradually build the order of courses by removing nodes from the queue and adjusting in-degrees, adding new nodes with in-degree 0 to the queue.

Steps:

Construct the graph and compute in-degrees for each course.
Use a queue to perform a level-by-level traversal, akin to BFS.
Track the order and check if all nodes (courses) are processed.

Code:

Complexity Analysis

Time Complexity: O(V + E), where V is the number of courses and E is the number of prerequisite pairs.
Space Complexity: O(V + E) because of the adjacency list and degree array.

Course Schedule II

Ashish Pratap Singh

Problem Description

Example 1:

Example 2:

Example 3:

Constraints:

Solve it on LeetCode

Approaches

1. DFS-Based Topological Sorting

Intuition:

Steps:

Code:

2. Kahn’s Algorithm (BFS-Based Topological Sorting)

Intuition:

Steps:

Code:

Get Premium