All Ancestors of a Node in a Directed Acyclic Graph | 3 Approaches | Leetcode 2192 |codestorywithMIK
Vložit
- čas přidán 27. 07. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 51st Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good Graph practice problem : All Ancestors of a Node in a Directed Acyclic Graph | 3 Approaches | Thought Process | Leetcode 2192 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : All Ancestors of a Node in a Directed Acyclic Graph | 3 Approaches | Thought Process | Leetcode 2192 | codestorywithMIK
Company Tags : will soon update
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/all-anc...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using DFS
Time Complexity: 𝑂(𝑛×(𝑛+𝑚))
Space Complexity: O(n+m)
In this approach, the algorithm performs Depth-First Search (DFS) from each node to find its ancestors.
The adjacency list representation of the graph is used to keep track of the edges. For each node,
a DFS is initiated to traverse its descendants, marking the ancestors along the way. This approach
ensures no duplicate entries by checking if an ancestor has already been recorded.
Approach 2: Reversing the Graph + Using DFS
Time Complexity: 𝑂(𝑛×(𝑛+𝑚))
Space Complexity: O(n+m)
This approach involves reversing the graph so that for each edge is reversed. The algorithm then uses DFS from each node in the reversed graph
to find all nodes that can reach the starting node, which effectively gives all the ancestors of the starting node. The ancestors are
collected by traversing the visited nodes for each DFS run.
Approach 3: Using Topological Sorting
Time Complexity: O(n + m + n^2 + nlogn)
Space Complexity: O(n^2+m)
In this approach, the algorithm first performs a topological sort on the graph. Nodes are processed in topologically sorted order,
ensuring that each node's ancestors are processed before the node itself. An adjacency list represents the graph, and an in-degree array
keeps track of incoming edges to perform the topological sort. After sorting, a set-based approach is used to accumulate ancestors efficiently,
followed by converting the sets to sorted lists.
Summary of Differences
DFS-based Approaches (1 & 2):
Both DFS-based approaches have similar time and space complexities.
Approach 1 does not reverse the graph, while Approach 2 does.
Both approaches use DFS to find and mark ancestors but differ in how they initialize and use the graph representation.
Topological Sort Approach (3):
This approach leverages topological sorting to process nodes in a specific order, ensuring that ancestor information is propagated correctly.
It includes additional steps to sort the ancestor lists, contributing to its higher space complexity due to maintaining sets and sorting lists.
This method can be more efficient in practice when dealing with large acyclic graphs due to the structured processing order of nodes.
✨ Timelines✨
00:00 - Introduction
3:00 - Brute Force
5:19 - Approach-1
12:24 - Coding Approach-1
17:20 - Approach-2
21:16 - Coding Approach-2
25:41 - Approach-3
38:25 - Coding Approach-3
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Hi Mik bhai,
Can you please make a video on "How to judge acceptable TC of a question by looking at constrains".
n > pow(10,8) ---> O(logn) || O(1)
n O(n)
n O(nlogn)
n O(n2)
n O(n3)
n O(pow(2,n))
n O(n!)
I was waiting for your video since 10am. I have made thought process of same. but couldn't implement it. Which thought process i have made, because of you Mik. thank you! Jai coding
i only watch because of u r explaination and java code in the github, so please dont stop it. it increases the views
I intuitively coded the 3rd approach but ye topological order mei sort hone wala catch nai pta tha isliye only 36 testcases worked aur uske bad aapki video dekhi, exact wohi problem ka solution batadia apne 🫡🫡
Mast explain kara mere bhai. Teeno approaches
bhaiyya if possible partition dp concept videos chaiye..thank you
Agree
topo sort is love bhaiya
was lookin for it!
Can't believe I am able to solve graph qns on my own. thank you guruji
Thanks a lot bhaiya ❤❤ Was able to solve this using the topological sort approach on my own Thanks to your graphs playlist 😊
Bhiya ,[ merge k sorted array using heap ] ko v explain kr dijiye if possible..
Done. Topological sort was very good
Bhaiya please ek ordered DSA sheet aur playlist banao if possible. Along with all concepts and problems videos for each topic. For example in binary trees playlist, pehle traversals aur concepts videos nahi hai toh mere jaise beginners ke liye thoda samajhna tough ho jata hai. Iss kaam mein help chahiye toh iss community mein baaki students help kar sakte hai. DSA sheet abhi na bhi ho toh chalega, bas playlists complete karwa do saare topics ke concepts ke.
Man, i solved it by myself but i am here to check your approach
hey you should make a crash course on each topic, it'll surely get views and would be helpful for everyone , with time stamps and pre written code...
past videos are there with a question and not every time that's needed..for example i wanted to just know about topological sort , i would rather watch a 13 minute video than a 26 minute one..
think about it please...
Thankyou Sir!
Please make a video on rod cutting problem, dynamic programming... thanks in advance and thanks again for the way of explaination.
refer @aditya verma's DP playlist...
7:45 how are you sure that to check only last element? can't it be that it might have repeated in even before the last one?
Done 🙌
please consider discussing about Time Complexity also.. rest everything is fine!!
Bhaiya Time Complexity of last approach explain kardo pls..
i would suggest ki just for 2 min , explain the code like of topological sort, it can work as revision also for others
because else we will be jumping from here and there unless if we are watching the playlist from the start...
why I said that is, because as a java programmer, sometimes it gets a bit difficult to follow through,
anyways someday I will watch your playlist from the start, so it'll become easier then I guess
Bhai TC of the last solution is not explained
WHAT IS THE TIME COMPLEXITY OF THE THIRD APPROACH? ANYONE ..?
Bhaiya aapne *palindrome substring* ka *blue print* batya tha uske *variant karwao*
Coming tomorrow ❤️
@@codestorywithMIK Bhaiya, ek baar Leetcode 2035 bhi karva dijiye...honest request to you🙏🙏
which question in playlist of tological sort
czcams.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=PhlXo940AMrH8G0w
sir 2 ka ancestor 7 nhi ho sakta hai
Yes you are right.
Can anyone tell me, why this doesn't work??
vectorans;
void dfs(int node, vector&vis,vectoradj[],int par)
{
vis[node]=true;
for(auto&it:adj[node])
{
if(!vis[it])
{
ans[it].push_back(node);
dfs(it,vis,adj,node);
}
}
}
///////////////
vector getAncestors(int n, vector& edges)
{
vectoradj[n];
for(auto&edge:edges)
adj[0].push_back(edge[1]);
ans.resize(n);
vectorvis(n,false);
for(int i=0;i
class Solution {
public:
vector getAncestors(int n, vector& edges) {
vector adj[n];
vector indeg(n , 0);
for(auto ele:edges)
{
adj[ele[0]].push_back(ele[1]);
indeg[ele[1]]++;
}
queue q;
for(int i = 0 ; i < n ; i++)
{
if(indeg[i] == 0)
q.push(i);
}
vector ans(n);
while(!q.empty())
{
int node = q.front(); q.pop();
set my = ans[node];
for(auto ele:adj[node])
{
ans[ele].insert(node);
for(auto it:my)
ans[ele].insert(it);
indeg[ele]--;
if(indeg[ele] == 0)
q.push(ele);
}
}
vector res(n);
for(int i = 0 ; i< n ;i++)
{
for(auto ele:ans[i])
{
res[i].push_back(ele);
}
}
return res;
}
};
7 ka ancestor 2 bhi ho sakta hai
Yep, my bad. Apologies for the typo
No bhaiya I just ask
Can you tell me what is wrong in
class Solution {
public:
vector getAncestors(int n, vector& edges) {
sort(edges.begin(),edges.end());
vector ans(n);
for(int i=0;i
because how do you know , (even after sorting the edges)
that "from" has only that much ancestors at the very first traversal , so it first need see all the edges to see who are its ancestors
@@tusharnanda3885 Ok Thanks
7 ka Ancestor 2 ho shakata hai ?? shayad vo likhana bhool gaye hai??
Yep, my bad. Apologies for the typo
@@codestorywithMIK sir kya app muje DSA ke sabhi concept ki dedicated playlist share kar shakate ho
Segment Tree - czcams.com/play/PLpIkg8OmuX-K1qUIQToCllUO0UIKXt8dB.html&si=c3uRh732o0htcY2t
Recursion Concepts - czcams.com/play/PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM.html&si=ZX6nDydK40MNyVAU
Bit Manipulation - czcams.com/play/PLpIkg8OmuX-I-t2eiSxfO0UjiLhmNGfon.html&si=KVBZAfQYnKzcuzU9
DP Concepts - czcams.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html&si=LdRFFNgSfIhhEFA2
Graph Concepts - czcams.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=bBjx6JXrLQUQB--U
Design Data Structure - czcams.com/play/PLpIkg8OmuX-JW5294URE-iwVhl_tdWEP5.html&si=Yt_nPZeY7aZHfAZk
Backtracking - czcams.com/play/PLpIkg8OmuX-KJPC18SGiRUzJQAYo839ox.html&si=fdKmQi7B8WrmHFJz
Maths - czcams.com/play/PLpIkg8OmuX-Js_8KIvsQskF7-RvCGg4nr.html&si=NCZR06wAI7SfcXgL
Heap - czcams.com/play/PLpIkg8OmuX-IkxvvfOeZp-Ot0UWHMGAT-.html&si=X_t7iIpKN4-2rXae
Stack - czcams.com/play/PLpIkg8OmuX-IA6_cJxfTYCmnv1jkqox47.html&si=we_VKtodOtb3237X
Trie - czcams.com/play/PLpIkg8OmuX-I99uuP2BZOz4mI_lms4gVG.html&si=47lipddWjOevZq4F
Graph Qns - czcams.com/play/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO.html&si=1haCaFjPJKlpdg5e
DP Qns - czcams.com/play/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO.html&si=1haCaFjPJKlpdg5e
Strings - czcams.com/play/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO.html&si=1haCaFjPJKlpdg5e
LinkedList - czcams.com/play/PLpIkg8OmuX-LH398-_ZcuHiRueOdsJbXU.html&si=cmTro9NOIBeiRLM_
Greedy - czcams.com/play/PLpIkg8OmuX-LH398-_ZcuHiRueOdsJbXU.html&si=cmTro9NOIBeiRLM_
Binary Search - czcams.com/play/PLpIkg8OmuX-LkgtrEF7eyyYWJM3m5tVQY.html&si=xcLhnsCrdDINDVIN
Sliding Window - czcams.com/play/PLpIkg8OmuX-J2Ivo9YdY7bRDstPPTVGvN.html&si=d3iBejdgeqrDgGzw
Binary Tree - czcams.com/play/PLpIkg8OmuX-K23LhcamOcDlTBisiNJy5E.html&si=Ke_ZZfMt5hXnuA-J
Arrays - czcams.com/play/PLpIkg8OmuX-K6A0sEPFxOSJh4_AjCGAFf.html&si=vLcm9j-WrQabjbVZ
@@codestorywithMIK Tussi GREAT ho!!
@@codestorywithMIK Thank you Sir
jai shree ram mik bhaii
❤️❤️❤️🙏🙏😇😇😇 Jai Shree Ram ❤️❤️❤️🙏🙏😇😇😇