Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIK
227Whatsapp Community Link : https://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) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/find-ce...
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 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