Medium — Graph | Topological Sort | BFS | Queue

The Problem

Given a number of courses and their prerequisites, return the order in which courses should be taken to complete all courses, or an empty array if impossible due to circular dependencies.

Approach

Uses Kahn’s algorithm for topological sorting by building a directed graph from prerequisites, tracking in-degrees of each node, and repeatedly removing nodes with zero in-degree while maintaining the order. If all courses are processed, a valid ordering exists; otherwise, there’s a cycle.

Time: O(V + E) · Space: O(V + E)

Code

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = {i: [] for i in range(numCourses)}
        in_degree = [0] * numCourses
        order = []

        # Construct the graph and count in-degrees
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Initialize a queue with nodes having in-degree zero
        queue = collections.deque(
            [course for course, degree in enumerate(in_degree) if degree == 0]
        )

        # Perform topological sorting and update in-degrees
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        # If the order doesn't contain all courses, there's a cycle
        return order if len(order) == numCourses else []

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment