Unpack the core of topological sort, focusing on ordering dependencies and resolving compilation sequences efficiently.

Coding

Topological Sort

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# Statement

You are given an integer, `num_courses`, representing the total number of courses you need to complete, labeled from `0` to `num_courses - 1`.

You are also given a `prerequisites` array, where `prerequisites[i] = [a[i], b[i]]` indicates that you must take course `b[i]` first if you want to take the course `a[i]`. For example, the pair $[1, 0]$ indicates that to take course $1$, you have to first take course $0$.

Return TRUE if all of the courses can be finished. Otherwise, return FALSE.

**Constraints:**

- $1 \leq$ `num_courses` $\leq 1500$
- $0 \leq$ `prerequisites.length` $\leq 1000$
- `prerequisites[i].length` $= 2$
- $0 \leq$ `a[i]`, `b[i]` $<$ `num_courses`
- All the pairs `prerequisites[i]` are unique.

# Solution

Initialize the hash map with the vertices and their children. We'll use another hash map to keep track of the number of in-degrees of each vertex. Then we'll find the source vertex (with $0$ in-degree) and increment the `counter`. Retrieve the source node's children and add them to the queue. Decrement the in-degrees of the retrieved children.
We'll check whether the in-degree of the child vertex becomes equal to zero, and we increment the `counter`.
Repeat the process until the queue is empty.

> **Note:** The in-degree is the number of edges coming into a vertex in a directed graph.

The primary purpose of finding a vertex with 0 in-degree is to find a course with a pre-requisite count of 0. When we take a course, say a (that is the pre-requisite of another course, say b), we'll decrement the in-degree of b by 1, and if the in-degree count becomes 0, we can say that the b's pre-requisites have been completed.


The slide deck below illustrates the algorithm above, where `num_courses = 6`:




Let's solve the Course Schedule problem using the Topological Sort pattern.

Solution: Course Schedule

Statement▼

Solution

Solution: Course Schedule

Statement▼

Solution