LeetCode 207 & 210: Course Schedule I & II | Topological Sort | Kahn's algorithm - Interview Ep 78.2

preview_player
Показать описание

This is the 2nd part of topological sort talking about applying Kahn's algorithm to solve LeetCode problems.

Problem link on LeetCode:

⭐ Support my channel and connect with me:

Algorithm explained:
we first find a set of vertices that don't have any incoming edges;
then we loop through these vertices to remove any edges using them as incoming vertices;
along the way, if we find other vertices don't have any incoming edges any more, we'll add them into this set as well;
until this set becomes empty, we break out of this loop;
then we check if there are still any edges there, if so, this is a DAG (Directed Acyclic Graph), it's impossible to find such a topological ordering.
Otherwise, return the order.

Time complexity: O(V+E) (V is the number of vertices and E is the number of edges in the given graph)

// TOOLS THAT I USE:

// MY FAVORITE BOOKS:

My ENTIRE Programming Equipment and Computer Science Bookshelf:

And make sure you subscribe to my channel!

Your comments/thoughts/questions/advice will be greatly appreciated!

#Kahnsalgorithm #graphsearch #topologicalsorting #softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures
Рекомендации по теме
Комментарии
Автор

Thank you for making this video! This is probably the best video to understand topological sort! I am just curious how do you have dark mode on LeetCode?

joellew
Автор

Hey! I saw on your LC that you go or went to the University of Minnesota? I am going to be an incoming freshman there

ramko
Автор

Excellent Sir !
But one query is, why we used HashSet here we can also Queue here normal BFS approach ?


📌 Code Using Queue

class Solution {
public boolean canFinish(int n, int[][] p) {

if(p.length==0) return true;

//initialize indegree
int inDegree[]=new int[n];

//indegree calculation
for(int[] c:p)
inDegree[c[0]]++;


Queue<Integer> queue=new LinkedList<>();

for(int i=0;i<n;i++){
if(inDegree[i]==0)
queue.offer(i);
}

if(queue.isEmpty())
return false;

while(!queue.isEmpty()){
int course=queue.poll();
for(int[] pre:p){
if(pre[1]==course){
inDegree[pre[0]]--;
if(inDegree[pre[0]]==0)
queue.offer(pre[0]);
}
}
}

for(int c:inDegree)
if(c!=0)
return false;

return true;
}
}

karankanojiya
welcome to shbcf.ru