NeetCode #604LC-277MediumGraphsNC Algo100
← Back to All Problems#604 · #277 · Find the Celebrity(搜寻名人)
📌 Problem Statement & Constraints
This is an interactive problem. In a party of
n people, a celebrity is known by everyone else but knows nobody. Given knows(a, b) returning whether a knows b, find the celebrity's label or -1. Constraints: 1 <= n <= 100; at most 3n calls to knows.💡 Core Algorithmic Approaches
- Candidate elimination: start with candidate 0 and scan the others. If
candidateknowsi, thencandidatecannot be the celebrity, so adopti. - After one pass, at most one candidate remains.
- Then verify: the candidate must know nobody and be known by everyone else.
- This uses at most
3n - 4calls, within the budget.
💻 Benchmark Python3 Implementation
class Solution:
def findCelebrity(self, n: int) -> int:
candidate = 0
for i in range(1, n):
if knows(candidate, i):
candidate = i # candidate knows someone -> not the celebrity
# verify the candidate
for i in range(n):
if i == candidate:
continue
if knows(candidate, i) or not knows(i, candidate):
return -1
return candidate⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) calls to knows: about 2n in the verification plus n - 1 in the elimination.
💾 Space Complexity
O(1): one candidate index.
⚠️ Interview Pitfalls & Follow-ups
- Comparing knowledge counts without elimination: you would need to count for every person, using O(n^2) calls.
- Skipping the verification: the elimination leaves a single candidate, but it may not be a celebrity.
- Checking
knows(i, candidate)in the elimination loop: the elimination only needs one direction. - Forgetting the self-comparison in verification:
knows(c, c)is not queried.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.