Problem 1791

Abstract / Summary

Find the node connected to all other nodes in a star shaped graph.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
11 lines | 317 bytes | submitted December 20, 2023 | GitHub   22% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 87% (500k+ submissions).

Typical patterns to solve this problem:
  • Graph Theory
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.96 | σ = 1.84

Complexity Analysis

Time: constant
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
32 links | 19 authors | 10 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

20 solutions   December 20, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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