Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIK
Vložit
- čas přidán 25. 06. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 44th Video of our Playlist "Binary Search Tree : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve an easy practice problem : Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | 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 : Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIK
Company Tags : MICROSOFT
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/find-ce...
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 a Map
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(n)
This approach uses a hashmap to keep track of the degree of each node in the graph. The steps are as follows:
Initialize Map: Create a hashmap to store the degree of each node.
Count Degrees: Iterate through the list of edges, incrementing the degree of each node involved in an edge.
Find Center: Iterate through the entries in the hashmap to find the node whose degree is equal to the number of edges. This node is the center of the star graph.
This approach has a linear time complexity because it processes each edge once and a linear space complexity because it stores the degree of each node.
Approach 2: Constant Time
Time Complexity (T.C): O(1)
Space Complexity (S.C): O(1)
This approach leverages the property of a star graph where the center node will appear in the first two edges. The steps are as follows:
Extract First Two Edges: Retrieve the first two edges from the list.
Compare Nodes: Compare the nodes in the first and second edges to identify the common node. This common node is the center of the star graph.
This approach has a constant time complexity and constant space complexity since it only involves checking two edges and does not require any additional data structures.
✨ Timelines✨
00:00 - Introduction
#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
Time complexity O(1)
Just check common integer in first two edges
bhaiyya maine apke system design playlist pura kiya..wo khatam ho gaya gya..apne ab tak HLD he bayataya..LLD kab ayega
MIK bhaiya app vector na lekar bhi kar sakte the like
if(edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1]) return edges[0][0];
else return edges[0][1];
Awesome 🙌
Thanks a lot bhaiya ❤️❤️
love your voice. itna early upload kardete ho. when do you sleep and wakeup ?
Simple one ☝️
Thank you 😊
Good explanation 👏 👍
damn bhai apke explanation ke saamne to ye bde bde creaters fail h kya hi smjhate ho
Make a playlist on bit manipulation
Bhaiya *palindrome substring* ka aapne *blue print* diya tha useke variant q karwaiye
Bro pls create a playlist on bit manipulation 😊
Sir we. Can also do it wth topological search too
Sir, Which software are you using for drawing and explanation?
Bhaiya, please make video on Leetcode 2035 using meet in middle approach. I dm'ed you on insta as well. I'm unable to solve that problem.
Sir please upload more segment tree videos.
Coming this weekend ❤️
@@codestorywithMIK Thank you bhaiya
@@codestorywithMIK thank you so much. Waiting
Uploaded 2 videos today -
czcams.com/video/VJ67kQHYbv8/video.htmlsi=tOEjVnH9g0fADfEh
czcams.com/video/qU4DAnv3o7g/video.htmlsi=w7bVVif3DmAgh0_k
@@codestorywithMIK thank you so much sir👌❤️❤️🙌
0:45 world government 🙂💀
I solved using adjacency list:
int findCenter(vector& edges) {
int n=edges.size();
vector adj(n+2);
for(int i=0;i
baaki nodes ki degree 1 hi kyun hogi ?
e.g. agar 1,3 edge hota , toh bhi toh ye star graph hi hota na ?
nahi.
@@gui-codes in that case what would that graph have been called?
@@aizad786iqbal Actually it's only as per what the problem has explained.
As per the problem, star pattern will be something like a node in center and remaining nodes connected to it.
i.e. centre me ek node hoga jo baaki saare nodes se connected hoga.
Total nodes = n
Centre waale node ko chodkar kitne nodes hue = n-1
So centre nodes n-1 nodes se connected hoga islie degree uski n-1 hogi.
And star pattern hai to sirf ek hi centre node hoga.
Please make video on " 741 Cherry Pickup "
Time O(1) and space O(1)
class Solution {
public:
int findCenter(vector& edges) {
if(edges[0][0] == edges[1][0]){
return edges[0][0];
}else if(edges[0][0] == edges[1][1]){
return edges[0][0];
}else if(edges[0][1] == edges[1][0]){
return edges[0][1];
}else if(edges[0][1] == edges[1][1]){
return edges[1][1];
}
return 0;
}
};
n-1 kyuuuu
Problem me mentioned hai ki star pattern aisa hi hoga ki centre me ek node hoga jo baaki saare nodes se connected hoga.
Total nodes = n
Centre waale node ko chodkar kitne nodes hue = n-1
So centre nodes n-1 nodes se connected hoga islie degree uski n-1 hogi.
And star pattern hai to sirf ek hi centre node hoga.
@@aws_handles ha ok