Hierholzer's Algorithm | Valid Arrangement of Pairs | Leetcode 2097 | Graph Concepts & Qns - 43
HTML-код
- Опубликовано: 3 дек 2024
- iPad PDF Notes Link - github.com/MAZ...
Whatsapp Community Link : www.whatsapp.c...
Hi Everyone, this is the 43rd video of our Playlist "Graph Concepts & Qns".
This is one of the very popular topics in Graph as well as a very important topic in Graph.
We had already studied Euler Path/Circuit theory in video-40, video-41 and video-42 of this playlist.
Euler Part-1 : • Euler Path | Euler Cir...
Euler Part-2 : • Euler Path | Euler Cir...
Euler Part-3 : • Euler Path | Euler Cir...
In this video, we will see what is Hierholzer's Algorithm is and how it helps to find the Euler Path in a Graph.
Problem Name : Hierholzer's Algorithm | Valid Arrangement of Pairs | Leetcode 2097 | Graph Concepts & Qns - 43 | Explanation + Code
Company Tags : will update later
My solutions on Github(C++ & JAVA) - github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Segment Tree Concepts Playlist : • Segment Tree | Introdu...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Video Summary :
The solution finds a valid Eulerian path in a directed graph represented by a list of pairs. It involves the following steps:
1) Graph Construction:
Build an adjacency list to represent the directed graph, while also tracking the indegree and outdegree of each node.
2) Start Node Identification:
Identify the starting node of the Eulerian path. The start node is the node where outdegree - indegree == 1. If no such node exists, use the first node from the input pairs.
3) DFS to Construct Eulerian Path:
Perform a depth-first search (DFS) using a stack to traverse the graph and construct the Eulerian path by removing edges as they are visited.
4) Result Construction:
Reverse the Eulerian path obtained from DFS and convert it into a list of consecutive pairs, which forms the valid arrangement.
This approach ensures that all edges are used exactly once, yielding a valid Eulerian path in the given directed graph.
✨ Timelines✨
00:00 - Introduction
#MIK #mik #Mik
#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 #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik
Euler Part-1 : ruclips.net/video/CeO0JEX4QAc/видео.html
Euler Part-2 : ruclips.net/video/i8h_O6u3DSc/видео.html
Euler Part-3 : ruclips.net/video/mw1mGKKR3QQ/видео.html
If you want to see DFS using Recursion - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Euler/Valid%20Arrangement%20of%20Pairs.cpp
Came here after watching
EULER PART-1,2,3
And guess what, i solved this problem.
You are my HERO ❤😢
THANKS A LOT
I can't thank you enough, MIK. Teachers like you are one in a million. God bless you. 💖
thanks for the helpful explanation, here is my approach in which results are constructed during the dfs, no need to separately create result:
const validArrangement = (pairs) => {
const result = [];
const graph = new Map();
const inOutCounts = new Map();
// Build the graph and track in/out degree counts
for (const [start, end] of pairs) {
if (!graph.has(start)) graph.set(start, []);
graph.get(start).push(end);
inOutCounts.set(start, (inOutCounts.get(start) || 0) + 1);
inOutCounts.set(end, (inOutCounts.get(end) || 0) - 1);
}
// Find the starting point of the Eulerian path
let startNode = pairs[0][0]; // Default to any node in pairs
for (const [node, count] of inOutCounts.entries()) {
if (count === 1) {
startNode = node;
break;
}
}
// Depth-first search (DFS) to construct the Eulerian path
const dfs = (node) => {
const edges = graph.get(node);
while (edges?.length) {
const nextNode = edges.pop();
dfs(nextNode);
result.push([node, nextNode]);
}
};
dfs(startNode);
// Reverse the result to return the correct order
return result.reverse();
};
Wow. Insane explanation. You are amazing
Aapse mast koi nhi samjhata , you're the best 💯
12:14 Hierholzer's Algorithm.
Thank You for this Amazing Video.
No doubt this question has a CP flavor in it
thanks bro, amazing explanation
31:27 - I also got the November badge. All thanks to you.
finally previous 3 videos complete dekhne ke baad iss final video pe pahuch gya 😂, Lekin believe me guys ye easy level program lagega jab previous 3 videos cover karloge tab, Thankyou sir for giving this easy kahani of the code...
bhaiya please help me i solved aroud 350+ problems on leetcode , but i am unable to do any new problem , i am just able to do problem which i solved in past , and when i move to next topic i forget the previous topic please help how to overcome with this problem .
It's not how many you solve, it's how you solve
I have solved around 500 problems in leetcode. So what i say is when u solve a particular problem u are thinking it as a separate question. Instead try to think of it as a pattern
For example, u may know the dfs and bfs. But what is more important is u must know what situation demands the use of such algorithm.
Instead of aiming to solving a question try to think of what scenario of question made u use some algorithm so that in future when a new question has some similar scenario u can solve there
Damn both videos in one day.
Thank you so much. I was waiting for this.
Very helpful❤
Hi Mik,
Great Video as always! thank you so much for this graphs playlist!
Just one observation in 27:37 , we can not take a random value as the startNode , because there was a TC where the graph was an EC and if we take a random value then the if condition will not satisfy (outdegree - indegree == 1) as for EC (as you have explained in the previous videos) all the indegrees and outdegrees will have difference 0. The startNode value should be one of the nodes as you have suggested, but not a random value.
Yes yes. By random i meant any random value from the nodes.
Thank you for mentioning 😇❤️
Thank you so much. Was waiting
First 🎉❤
Bhaiya can you please add some problems in segment tree playlist no one have taught that topic in great detail 3-4 videos will be sufficient to grasp the topic humble request
Great analysis, thank you! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (alarm fetch churn bridge exercise tape speak race clerk couch crater letter). How can I transfer them to Binance?
But why did you chose pairs[0][0] as start value because in the 2nd example test case there is no node with the outdegree - indegree as 1.
So how can we decide start node here
If there is no node with outdegree -indegree = 1,
Then it means it’s an Euler Circuit. And in that case any node can be treated as start node.
same doubt and got answer
bhaiya in case there is multiple path form a node we have to choose a path first which will lead to that node again like in the case of 1 2 , 2 3, 3 4 , 4 2, 2 5 , 5 2 , 2 6
when we reach to 2 we have three path so we have to choose path to 6 atlast but you have done just dfs which will randomly choose a path how its working please can you explain??
And thank you for your great videos helping me greatly.
so whats happening is that postorder is taken into consideration. The node which does not have any outgoing edges will be accounted first no matter what. for example if we have 1-->2 1-->3 2-->1 .....if wwe start from 1 then we will end up logging 3 at first as we fill keep diving deeper and deeper until there is no edge left from current node. once we find it we log it somewhere and make the euclidean path. so 3 will come first.... and in the end we reverse this logged path
Hi Mik,
I've implemented the same approach but used DFS in a recursive manner. However, I'm curious how your case no. 8 isn't failing. For instance, if the starting node has an out-degree of 3, how do you decide which node to pick first for traversal? My code seems to fail in such scenarios. I'm attaching my code below for reference. Thanks!
class Solution {
public int[][] validArrangement(int[][] pairs) {
Map adjList = new HashMap();
Map inDegreeOutDegreeDiff = new HashMap();
for(int[] pair : pairs) {
adjList.computeIfAbsent(pair[0], k -> new ArrayList()).add(pair[1]);
inDegreeOutDegreeDiff.put(pair[0], inDegreeOutDegreeDiff.getOrDefault(pair[0], 0) + 1);
inDegreeOutDegreeDiff.put(pair[1], inDegreeOutDegreeDiff.getOrDefault(pair[1], 0) - 1);
if(inDegreeOutDegreeDiff.get(pair[0]) == 0) inDegreeOutDegreeDiff.remove(pair[0]);
if(inDegreeOutDegreeDiff.get(pair[1]) == 0) inDegreeOutDegreeDiff.remove(pair[1]);
}
System.out.println(inDegreeOutDegreeDiff);
int source = pairs[0][0];
for(Map.Entry entry : inDegreeOutDegreeDiff.entrySet()) {
if(entry.getValue() == 1) {
source = entry.getKey();
}
}
List path = new ArrayList();
Map visited = new HashMap();
dfs(source, path, visited, adjList);
return path.toArray(new int[][]{});
}
private void dfs(int source, List path, Map visited, Map adjList) {
for(int adj : adjList.getOrDefault(source, Collections.emptyList())) {
if(!visited.computeIfAbsent(source, k -> new HashSet()).contains(adj)) {
path.add(new int[]{source, adj});
visited.get(source).add(adj);
dfs(adj, path, visited, adjList);
}
}
}
}
bro , postorder DFS is required for this algorithm , preOrder will fail the path.
@@anuragsekhri2315 i added nodes before dfs traversal that would avoid reversal hy I am geyting it wrong ?
public void dfs(List adj,int start,int end,int pairs[][],int i)
{
List neighbors=adj.get(start);
while(!neighbors.isEmpty()) {
int next=neighbors.remove(0);
pairs[i][0]=start;
pairs[i][1]=next;
dfs(adj,next,end,pairs,i+1);
}
}
Also bhaiya, this code gives TLE if I am using the recursive DFS function:
This code is givng TLE while if I am using stack, it doesnt:
class Solution {
public:
void dfs(unordered_map& mp, int node, vector& res) {
while (!mp[node].empty()) {
int nextNode = mp[node].front();
mp[node].pop_front();
dfs(mp, nextNode, res);
}
res.push_back(node);
}
vector validArrangement(vector& pairs) {
unordered_map indegree, outdegree;
unordered_map mp;
for (auto it : pairs) {
mp[it[0]].push_back(it[1]);
indegree[it[1]]++;
outdegree[it[0]]++;
}
int findStart = -1;
for (auto it : outdegree) {
if (it.second > indegree[it.first]) {
findStart = it.first;
break;
}
}
if (findStart == -1) {
findStart = pairs[0][0];
}
vector res;
dfs(mp, findStart, res);
reverse(res.begin(), res.end());
vector ans;
for (int i = 0; i < res.size() - 1; ++i) {
ans.push_back({res[i], res[i + 1]});
}
return ans;
}
};
Please see the Pinned comment for DFS recursive ❤️🙏
Somehow, it seems like using a deque instead of a vector seems to cause the TLE
can someone explain how it is working if outdegree is more than 1 ?
Bhai maine pehle video dekke chod diya tha ki baad mai jaaye badge par jab ismai apne bola ganta mushkil nahi lagne wal, thoda hosla aya hai, abhi video chal raha hai par mentality set hogaya ki chalo badge lelete hai
Same. But Euler k videos dekhne k baad ye problem bahot easy laega honestly.
Please help me sir with this test case .
pairs = [[1,2],[1,3],[2,1]]
1 -> 2, 3
2 -> 1
I'm using DFS but it's failing. as I'm not able to decide where to go from 1 , should i go to 2 or 3.
that doesn't matter. you can choose any
@@aadarshjha9256 no brother if i'll choose 3 definitely i will not get my answer
@@kumkumslab5811 you will get sis..try to dry run
while (!stack.empty()) {
int node = stack.back();
cout
@@kumkumslab5811 1->3(as no node left for 3, push it to path)
again, explore 1, 1->2->1(no node left for 1 so push it to the path),
lastly we are left with 2 and 1, push both to path.
final(3,1,2,1)
bro explain java code also in video
I thought to find the number with freq one, that one will be starting and one will be ending,
then sort the array on the basis of starting,
I have the starting point, find that pair, add it to my resultant array search using binary search
then ending point of will be the start of next will search that using binary serach
over all
TC O(n) searching start + O(nlogn) sorting on the basis of start + O(nlogn) to find next pair for my current
SC O(n) resultant
What do you think about this approach, didn't think of graph for this.
Sir graphs mei problem horahi hai, can you suggest me something ??? Like non linear DS ke questions 3 percent hi kara aaj tak
I would suggest you to first study the concepts of Graph, then these wouldn’t be difficult.
Concepts playlist - ruclips.net/p/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY&si=M1Hs-8lFl_xl04Av
bhaiya, in the starting part of the question, it's mentioned that it is a 2d array. Say we see this question, how would i even understand that it is related to graphs?
Hi there,
Actually problems like these need prior understanding of some concepts. For example: this one needs a prior understanding of Euler Graphs.
So it’s totally fine if you hit a new concept. In such cases, i simply go through the new concept, understand it and solve 4-5 Qns to get it clear and explore different variants.
This will help to grow further
@codestorywithMIK Thanks bhaiya
i am here after p1, p2 and p3
@codestorywithMIK, This is frustrating, In the morning, when I tried this problem, I was able to figure out by observation that what should be the start point. But after that I just got blank and couldn't just think that this now just requires a simple DFS nothing else. Can you please point out why such thing happens?
Background : I am an experienced developer and have been solving Leetcode problems since a long time. Also have solved numerous DFS problems in past. Seriously need help. Even yesterday PTOD, Just in few minutes I was able to figure out that this will be done with Dijikstra's Algo but couldn't figure out that odd and even condition. Can you please help?
Hi there,
Actually problems like these need prior understanding of some concepts. For example: this one needs a prior understanding of Euler Graphs.
So it’s totally fine if you hit a new concept. In such cases, i simply go through the new concept, understand it and solve 4-5 Qns to get it clear and explore different variants.
This will help to grow further
@@codestorywithMIK Okay thanks a lot. yeah you explained well about Euler Graphs, especially the 3rd video. Keep up the good work. Yes agreed, with you that , This will require knowledge that this is a Euler Graph and all the edges need to be visited just once and we just need to understand that this requires graph traversal. Thanks a lot. Keep up the good work. You have a great method to explain things. I do watch your videos everyday, even if I have solved the problem by myself. One more request can you please add more videos in your System Design Intermediate play list? That list is also a great list.
Bro share the cat pic who is meowwwwing in the background plz
Here you go -
instagram.com/reel/DCboG5ORJoh/?igsh=emdxZ3VtcWNrbGNt
😇❤️
sir vo startnode ko pair[0][0] kyu liya samaj nhi aaya ???? please help
I just randomly chose a value for startNode. It will get updated inside for loop
bro , in case if startnode can't assign than it will take pairs[0][0]
@@codestorywithMIK o got it , thankyou
Bro i really appreciate your work ❤, but it would be great if you use formal language . It doesn't sound good when you use some words which you aren't supposed to, somewhere it doesn't sound professional . NO OFFENSE !! 🙌🙏
Dear Akash,
Apologies if you felt so.
I will take care of this.
Appreciate your feedback ❤️🙏