⚡Flashcard Drill➔
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

  1. Candidate elimination: start with candidate 0 and scan the others. If candidate knows i, then candidate cannot be the celebrity, so adopt i.
  2. After one pass, at most one candidate remains.
  3. Then verify: the candidate must know nobody and be known by everyone else.
  4. This uses at most 3n - 4 calls, 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems