Course Schedule | Deadlock detection | Graph coloring | Leetcode
Vložit
- čas přidán 6. 09. 2024
- This video explains a very important programming interview problem which is, given a course schedule with prerequisites for each course, find if it is possible to take all the courses satisfying the prerequisites for each course. If it is possible then return TRUE otherwise FALSE.This problem is same as detecting a deadlock in a single resource instance distributed system.In such a system, if we have a cycle then we a deadlock.Therefore, this problem further reduces to finding cycle in a graph.I have shown the solution using graph coloring to detect cycle in a directed graph.At the end of the video, i have explained the CODE. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.co...
SIMILAR PROBLEMS:-
Detect cycle in a directed graph: • Detect cycle in a dire...
Detect cycle in an undirected graph: • Detect cycle in an und...
Sir, your videos are really helpful than a Paid Course❤
Thanks :)
Another great one. He's my new favourite.
Thanks :)
Overcomplicated with three colors. Why can't we simply use a boolean visited array and from each node to check if the current node was already included in the traveling path.
Your wish :)
@@techdose4u can we not use logic used for cloning graph ? where we look for visited node, in this case as well we can do near to similar approach ? tree/graph problems are near to similar but why choose different way of solving ? we can do with minimal changes.
just a note if you had a processing state as 1 and processed one as 2 would be more understandable since it is in increasing order. BTW nice explanation. Good effort.
Dude.. You are better than all of college lectures..
Thanks ☺️
Thanks a ton. Now I am able to solve the same problem using DFS and BFS.
Welcome :)
A very similar way for using the unvisited, processing and processed is to use white - grey - black colors respectively
I have coded this in Java. Posting my code below.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// to make adj matrix take ie Graph representation : (Adjacency list)
List output = new ArrayList();
/*We convert the list of course pairs to a directed graph with an edge u->v that represents a "pre-requisite to" relationship. Thus if we have the pair [0,1] (1 is a pre-requisite to 0), then we will have the following edge in our graph : 1->0
//Note: We consider the adjacency list representation over an adjacency matrix, considering that the graph might be sparse.*/
for(int i=0;i 1
1 > 2
2 > 3
so , in the following loop we build this
*/
for(int[] prereq : prerequisites) {
int coursePrequisite = prereq[1];
int currentCourse = prereq[0];
List prqCourses = output.get(currentCourse);
prqCourses.add(coursePrequisite);
}
/*
we use color coding in graph
following are the indications
0 : unvisited
1 : processed
2 : processing
*/
int[] visited = new int[numCourses];
// for every node(which represents a course) in the graph
for(int i=0;i
At first it took a lot of time but I am happy I made it,
Great :)
Keeping going sir... Very helpful posts🙏🙏♥️
Thanks :)
@@techdose4u Can you please check the playlists once.The playlists contains repetitive videos and increases the count.
Sir why u used processed and processing
Why not simple cycle detection
Well, we can also implement it using in degree I.e topological sort..
Correct.
Yet another amazing video! Thank you
Welcome :)
Best explanation... Thanks a lot for investing your time in spreading knowledge.
Welcome :)
It would be more clear if there is an example of graph containing a cycle. Anyways your explanation is awesome 🙌
U dint give it because I don't want to explain how to find cycle. My main intention was to explain why are we using 3 states 0,1,2. Cycle finding is already explained in other videos.
The arrows are drawn in the wrong direction.
Your explanation us very good , It would be helpful if you explain Time and Space complexity too.
Thanks. I will try
Java solution (Your runtime beats 100.00 % of java submissions)
class Solution {
public boolean iscyclic(ArrayList[] graph,int[] visit,int curr)
{
if(visit[curr]==2)
return true;
visit[curr]=2;
for(int i=0;i
Nice 👍
MY PROGRAM:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses ==0 || prerequisites.length == 0)
{
return true;
}
HashMap map = new HashMap();
for(int i=0;i
Excellent sir 👏
If course A requires course B to be a prerequisite, it should be course B pointing to course A, not the other way around. (B --> A).
why we need graph , it should be solved by linkedlist cycle detection? there is no mention of multiple prerequisites course for a course
you are a amazing professor
👌👌👌👌Very clear👌👌👌👌
👍
this tutorial is amazing!
Awesome One. Your way of explaining the problem, by breaking it down is really good. Keep up the good work.
Thanks
Time and Space Complexity?
great video sir ! Thx u made it so simple
Welcome :)
Using Topological Sort ->
class Solution {
public:
bool canFinish(int n, vector& pre) { // n = no of vertices
int edge=pre.size();
vector< vector > adj(n,vector ());
vector< int > indegree(n,0); // incoming edges on a vertex
for(int i=0;i
I also used the same approach, but instead of an array, I maintained two set processing, processed. But I think using Kahn's algorithm we can get a more optimized solution.
Kahn's algo is also traversing each node and processing so the time should be same as this one.
Solution in Java
class Solution {
public boolean canFinish(int n, int[][] pre) {
ArrayList arr =new ArrayList();
for(int i = 0; i
No Failing case was discussed
What if there are multiple components of a graph??
not able to understand the code of line 25. how the directed graph is created ??please reply sir
Actually we are given a 2D array where we have 2 cols. 1st col is source and 2nd col is destination. I am just making an array of linked list where I am assuming the array index to be source and pushing the destination into the linked list. This keeps track of all adjacent nodes where they are destination and curr node is source. Please read adjacency list for clarity.
@@techdose4u thnku i got it..i was confused b/w vector of vectors and adjacency matrix..
Hey, I have a doubt...
If we use DFS for the given problem (3 --> 2 --> 0 --> 1) & let's assume there is a loop in between (3-->0) and the source node is 0, at the time when we reach node 3 after recursion, node 2, 0 & 1 will already be marked as PROCESSED. How we will find if there is a loop in between node 3 and node 0?
According to the explained logic, the node should be in PROCESSING state and if got visited again then we will consider this as loop.
instead of putting all questions in one playlist(interview programming questions),please make separate playlist topic wise
Topicwise playlists are also present.
@@techdose4u Can we have basics too.Because graphs are completely naive for some peoples
Yep...I will continue with graphs once leetcode challenges are over 😅
Why do you prefer adjacency matrix representation over adjacency list?
Beginner friendly maybe :) I always solve with list and not matrix.
Nice Videos, But Sir please add some more ads , your video interrupts the ads. :D
😂 I set to auto-generation mode. Please understand that free content will have to contain ads for sustainability.
Can you please explain the creation of directed graph once more?
bro can you please tell me why doesnt my code give the correct ans ? first i detected if there is a cycle in the directed graph. if yes then return blank array otherwise then i simply did topological sort and returned the answer. here is my code : findOrder is the main function here.
vectorans;
bool cycle(int node,vector&visited,vector&stack,vectoradj[])
{
visited[node]=true;
stack[node]=true;
for(int neighbour:adj[node])
{
if(visited[neighbour]==false)
{
if(cycle(neighbour,visited,stack,adj))
return true;
}
else if(stack[neighbour]==true)
{
return true;
}
}
stack[node]=false;
return false;
}
void topological_sort(int node,vector&visited,vectoradj[])
{
visited[node]=true;
for(int neighbour:adj[node])
{
if(visited[neighbour]==false)
{
topological_sort(neighbour,visited,adj);
}
}
ans.push_back(node);
}
vector findOrder(int V, int m, vector prerequisites)
{
bool iscycle=false;
vectoradj[V];
for(auto edge:prerequisites)
{
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
//PART 1 : Find out if cycle exists in this using kahn algorithm. if yes,then it is not possible.
vectorvisited(V,false);
vectorstack(V,false);
for(int i=0;i
It was a great tutorial sir. Can we apply the cycle detection algorithm used in an undirected graph ( by removing bidirectional edges )for this problem as well sir.?
I have already explained why we need directed graph in the video. Please follow that.
I meant can we use cycle detect algo which we use when in case of undirected graph for this problem too.
Both should work.
how can we approach the same problem by the use of topo sort.???
whats the time complexity?
First viewer and first comment
🖖
not able to understand the code of line 9. What are we trying to check?
Can we call this backtracking algorithm? because graph coloring adjacent nodes made more sense in Possible Bipartition problem. In this its backtracking and you are calling it coloring graph right?
Recursion in general is called backtracking. It is also using coloring concept due to maintaining 3 states like colors. But I said similar to graph Coloring and not exactly graph Coloring.
@@techdose4u oh ok, got it. thanks :)
Sir , plz start videos on weekly leetcode contest solutions
Currently not possible
Sir please tell me why we go for graph coloring way as its directed we could do by simple visited array. Im confusing why we switch this to find cycle in directed graph sir please rply !?
Hello Sir, can you please tell me what can go wrong if we use only a boolean visited array instead of processing and processed options ?
It will take N2 time. It will run. You need to maintain the states of the already processed elements. So, you need one more vector. Better to use just one integer vector maintaining all 3 state info.
can we use union find algorithm to detect cycle?
Yes.
linked lists can also be used i believe... plzz correct me if I am wrong.
If you use linked list then it should be an array of linked list to form your adjacency list. It will be cumbersome and so go with array.
@@techdose4u okk thanks
Can this algorithm be coded in iterative way i.e. without recursion?
Apply BFS for iterative approach.
Code Link : techdose.co.in/course-schedule-deadlock-detection-graph-coloring/
i'm a little confused, it looks to me like the directed graph is the same as the input to me. could anyone help clarify why the directed graph is needed?
Had the same question, did you figure out why? I thought the "prerequisites" was already an adjacency list.
Oh, now I realize, the input is actually always a "pair" with only two numbers each. Example, [[1,0],[0,1]]. This is neither an adjacency list nor an adjacency matrix.
And If there is no deadlock,if they ask you sequence of courses Topological Sorting will be the answer
Yea but they dint ask that. Simply they asked if it was possible to take all courses. So cycle detection is sufficient. In toposort, we will start processing with indegree 0 and hence order will be perfect but cycle detection can start anywhere. But order is not important here. So cycle detection is enough.
@@techdose4u Yeah thats why I mentioned "If"
can we calculate the frequencies of each element and frequency of any element is greater than 2 return false else true
will this work?
No beacuse same node can point more than one node. Otherwise we could also use the linked list to solve this problem.
@@shreshthsingh7744 oh okay thanks bro
bhai,,,arrows ulte rahenge na
If the code runs concurrently, will there be data race on the visited array?
The code can’t exactly run concurrently , unless if you use separate machines or something
THIS CODE IS TO FIND CYCLE IN DIRECTED GRAPH
can someone help to find the mistake in this code.
I use unordered map here to make a adjcency list
and visited is also taken as unordered_map.
template
class Graph{
public:
unordered_map adjList;
void addEdge(T u, T v, bool biDir=true){
adjList[u].push_back(v);
if(biDir){
adjList[v].push_back(u);
}
}
void Print(){
for(auto node : adjList){
cout
This is illegal, you can't post a solution today.
This is not a contest but just a casual challenge with solutions flooded all over the internet and in discussions as well. What do you want to point at? If someone wants help, they can get the entire code and explanation and also I never post videos of any live contest. So what's the deal?
what a banger
Bro, why your insta is private :P
Should it be public? I don't have any experience in insta 😅
@@techdose4u if you are sharing link here, it should be public, you are celebrity 😁
😅 Made it public now