All Ancestors of a Node in a Directed Acyclic Graph | 3 Approaches | Leetcode 2192 |codestorywithMIK
309Whatsapp Community Link : https://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) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/all-anc...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://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