Python 1791.py
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
# two edges are sufficient
a, b = edges[0]
c, d = edges[1]
# find duplicate
four = [ a,b,c,d ]
while four:
x = four.pop()
if x in four:
return x
Difficulty
and has an acceptance rate of about 87% (500k+ submissions).
Typical patterns to solve this problem:
- Graph Theory
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation determines the central node of a star-shaped graph. A star graph consists of one hub node connected to every other node, while no other connections exist. The algorithm leverages the fact that any two edges of such a graph must share the hub node. By examining only the first two edges, it isolates the repeated vertex, which is the required center.
Key Steps
Extract First Two Edges
The method begins by unpacking the first two edge definitions from the input list. Each edge is a pair of integers representing connected vertices.
a, b = edges[0]
c, d = edges[1]
Build Candidate List
All four vertex identifiers from the two edges are collected into a single list. This list serves as the pool from which the duplicate (the hub) will be identified.
four = [a, b, c, d]
Find Duplicate
A loop repeatedly removes the last element of the list and checks whether that element still appears elsewhere in the list. The moment a vertex is found that exists more than once, it is returned as the center.
while four:
x = four.pop()
if x in four:
return x
Edge Cases Handled
The algorithm gracefully handles the minimal valid input where the graph contains exactly two edges, which is the smallest configuration that still defines a star. By directly accessing edges[0] and edges[1], it assumes the presence of at least two edges, which aligns with the problem constraints. The duplicate detection loop works correctly regardless of the order of vertices within each edge; whether the hub appears as the first or second element of an edge, the in check will locate it. Additionally, if the two edges share both vertices (an impossible scenario for a proper star but still a valid input for the function signature), the loop will still return the repeated vertex without error.
Performance Optimizations
The solution limits its work to a constant number of elements: only the first two edges are examined, and the candidate list never exceeds four items. This bounded scope eliminates the need to iterate over the entire edge collection, reducing the amount of data processed. The use of pop() removes elements from the end of the list in constant time, and the early return exits the function as soon as the hub is found, preventing unnecessary further checks. By focusing on a tiny fixed-size list, the algorithm achieves very fast execution for any permissible input size.
ELI5 - Simplified Explanation
Imagine all the friends in a classroom are holding hands. To find the friend who is the center of the circle, look at just the first two pairs of friends holding hands. Think of the first pair as two people in a line, and the second pair as another two people in a line. Because they are all connected to the center person, one of the friends from the first pair must also be holding hands with someone in the second pair. To find that special person, put those four friends in a group. Then, gently take them out of the group one by one. As each friend is taken out, look at the others still in the group to see if that same person is hiding there too. When finding that same friend waiting in the group, that is the person who stands in the center.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | Python | C++ | Java | TS | ||||||
| WalkCCC | Python | C++ | Java | ||||||||
| leetcode.ca | Python | C++ | JS | Java | Go | Rust | TS | ||||
| Progiez | Python | C++ | Java | ||||||||
| github | black-shadows | C++ | |||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| lkwq007 | Python | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| lkwq007 | Python | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python |
Videos
Similar Problems
- problem 2497: Maximum Star Sum of a Graph
Solved On The Same Day
- problem 1752: Check if Array Is Sorted and Rotated
- problem 1971: Find if Path Exists in Graph
- problem 1984: Minimum Difference Between Highest and Lowest of K Scores
- problem 2446: Determine if Two Events Have Conflict
- problem 2706: Buy Two Chocolates
- problem 2839: Check if Strings Can be Made Equal With Operations I
- problem 684: Redundant Connection
- problem 1008: Construct Binary Search Tree from Preorder Traversal
- problem 1026: Maximum Difference Between Node and Ancestor
- problem 1034: Coloring A Border
- problem 1625: Lexicographically Smallest String After Applying Operations
- problem 1765: Map of Highest Peak
- problem 2192: All Ancestors of a Node in a Directed Acyclic Graph
- problem 2477: Minimum Fuel Cost to Report to the Capital
- problem 2492: Minimum Score of a Path Between Two Cities
- problem 2596: Check Knight Tour Configuration
- problem 2658: Maximum Number of Fish in a Grid
- problem 827: Making A Large Island
- problem 1036: Escape a Large Maze
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality