Problem Description

You're at a party with n people labeled from 0 to n - 1. Among these people, there might be exactly one celebrity. A celebrity is defined as someone who:

• Is known by all other n - 1 people at the party
• Does not know any of the other people

Your task is to identify who the celebrity is, or determine that no celebrity exists at the party.

You can only gather information by asking questions in the form: "Does person A know person B?" This is done through a helper function knows(a, b) which returns true if person a knows person b, and false otherwise.

The goal is to minimize the number of questions asked (in terms of asymptotic complexity) while finding the celebrity.

The function should return:

• The celebrity's label (a number from 0 to n - 1) if a celebrity exists
• -1 if there is no celebrity at the party

Note that you don't have direct access to the underlying relationship graph. You can only use the knows(a, b) function to query relationships between people.

Intuition

The key insight is that when we ask if person a knows person b, we can eliminate one candidate from being the celebrity:

• If a knows b, then a cannot be the celebrity (celebrities don't know anyone)
• If a doesn't know b, then b cannot be the celebrity (everyone must know the celebrity)

This elimination property allows us to find a potential celebrity candidate efficiently. We can start with person 0 as our initial candidate and compare them with each subsequent person. Each comparison eliminates exactly one person from consideration.

For example, if we're comparing candidate 0 with person 1:

• If knows(0, 1) returns true, then 0 cannot be the celebrity, so we update our candidate to 1
• If knows(0, 1) returns false, then 1 cannot be the celebrity, so we keep 0 as our candidate

By doing this for all n people, we'll be left with exactly one candidate who hasn't been eliminated. This takes only n - 1 calls to the knows function.

However, this candidate might not actually be a celebrity - they're just the only person who wasn't eliminated. We need to verify two conditions:

1. The candidate doesn't know anyone else (check if knows(candidate, i) is false for all other people)
2. Everyone else knows the candidate (check if knows(i, candidate) is true for all other people)

This verification step requires at most 2(n - 1) additional calls to knows, giving us a total of O(n) calls, which is optimal since we need to verify relationships with all n people to confirm a celebrity exists.

Solution Approach

The solution implements a two-phase algorithm:

Phase 1: Find the Celebrity Candidate

We start by assuming person 0 is our potential celebrity candidate (ans = 0). Then we iterate through persons 1 to n-1:

ans = 0
for i in range(1, n):
    if knows(ans, i):
        ans = i

At each step, we check if our current candidate ans knows person i:

• If knows(ans, i) returns true, then ans cannot be the celebrity (celebrities don't know anyone), so we update ans = i
• If knows(ans, i) returns false, then i cannot be the celebrity (everyone must know the celebrity), so we keep ans unchanged

After this loop, ans holds the only person who could potentially be the celebrity. This takes exactly n-1 calls to the knows function.

Phase 2: Verify the Candidate

Now we need to verify that our candidate ans is actually a celebrity by checking two conditions:

for i in range(n):
    if ans != i:
        if knows(ans, i) or not knows(i, ans):
            return -1
return ans

For every other person i (where i != ans):

• Check if knows(ans, i) is true - if yes, ans knows someone and cannot be a celebrity
• Check if knows(i, ans) is false - if yes, someone doesn't know ans and they cannot be a celebrity

If either condition fails, we immediately return -1 indicating no celebrity exists. If we successfully verify all relationships, we return ans as the celebrity.

The verification phase uses at most 2(n-1) calls to knows (two checks for each of the other n-1 people).

Time Complexity: O(n) - we make at most 3n-3 calls to the knows function
Space Complexity: O(1) - we only use a constant amount of extra space

Example Walkthrough

Let's walk through a small example with n = 4 people (labeled 0, 1, 2, 3) where person 2 is the celebrity.

The relationship matrix looks like this (where 1 means "knows" and 0 means "doesn't know"):

     0  1  2  3
  0 [0, 0, 1, 0]  // Person 0 knows person 2
  1 [0, 0, 1, 0]  // Person 1 knows person 2
  2 [0, 0, 0, 0]  // Person 2 knows nobody (celebrity)
  3 [0, 0, 1, 0]  // Person 3 knows person 2

Phase 1: Find the Celebrity Candidate

Start with ans = 0 as our initial candidate.

• i = 1: Check knows(0, 1) → returns false (person 0 doesn't know person 1)

  • Since 0 doesn't know 1, person 1 cannot be the celebrity
  • Keep ans = 0

• i = 2: Check knows(0, 2) → returns true (person 0 knows person 2)

  • Since 0 knows 2, person 0 cannot be the celebrity
  • Update ans = 2

• i = 3: Check knows(2, 3) → returns false (person 2 doesn't know person 3)

  • Since 2 doesn't know 3, person 3 cannot be the celebrity
  • Keep ans = 2

After Phase 1, our candidate is person 2. We made 3 calls to knows.

Phase 2: Verify the Candidate

Now verify that person 2 is actually the celebrity:

• i = 0:

  • Check knows(2, 0) → returns false ✓ (celebrity shouldn't know anyone)
  • Check knows(0, 2) → returns true ✓ (everyone should know celebrity)

• i = 1:

  • Check knows(2, 1) → returns false ✓
  • Check knows(1, 2) → returns true ✓

• i = 3:

  • Check knows(2, 3) → returns false ✓
  • Check knows(3, 2) → returns true ✓

All checks pass! Person 2 is confirmed as the celebrity. We made 6 additional calls in Phase 2.

Total calls to knows: 9 (which is 3n - 3 for n = 4)

The algorithm correctly identified person 2 as the celebrity using O(n) calls to the knows function.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main phases:

1. First loop (candidate selection): Iterates from index 1 to n-1, making n-1 calls to the knows() function. This takes O(n) time.

2. Second loop (verification): Iterates through all n people to verify if the candidate is indeed a celebrity. In the worst case, this loop makes 2(n-1) calls to the knows() function:

   • For each person i where i ≠ ans, it checks:
     • knows(ans, i) - to verify the candidate doesn't know person i
     • knows(i, ans) - to verify person i knows the candidate
   • This results in at most 2(n-1) API calls

Total API calls: (n-1) + 2(n-1) = 3n - 3, which is O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• One variable ans to store the candidate index
• One loop variable i

No additional data structures are used that scale with the input size n, resulting in constant space complexity.

Common Pitfalls

Pitfall 1: Incorrect Candidate Elimination Logic

The Problem: A common mistake is misunderstanding why we update the candidate in Phase 1. Some might think:

• "If knows(candidate, i) is false, then we should make i the new candidate"
• Or implement redundant checks like also checking knows(i, candidate)

Why This is Wrong: The key insight is that with just ONE query knows(candidate, i), we can eliminate one person:

• If knows(candidate, i) == true: The current candidate CANNOT be a celebrity (celebrities know nobody), so we eliminate them and make i the new candidate
• If knows(candidate, i) == false: Person i CANNOT be a celebrity (everyone must know the celebrity), so we keep the current candidate

Incorrect Implementation:

# WRONG: Unnecessary extra check
candidate = 0
for i in range(1, n):
    if knows(candidate, i) and not knows(i, candidate):  # Redundant!
        candidate = i

Correct Implementation:

# RIGHT: Single check is sufficient
candidate = 0
for i in range(1, n):
    if knows(candidate, i):
        candidate = i

Pitfall 2: Incomplete Verification

The Problem: After finding a candidate, some solutions forget to verify BOTH conditions:

1. The candidate doesn't know anyone else
2. Everyone else knows the candidate

Incorrect Implementation:

# WRONG: Only checking one direction
for i in range(n):
    if candidate != i:
        if not knows(i, candidate):  # Only checking if others know candidate
            return -1
return candidate

Correct Implementation:

# RIGHT: Check both conditions
for i in range(n):
    if candidate != i:
        if knows(candidate, i) or not knows(i, candidate):
            return -1
return candidate

Pitfall 3: Off-by-One Errors in Loop Ranges

The Problem: Using incorrect loop ranges, especially starting from 0 when we should start from 1, or forgetting to exclude the candidate during verification.

Incorrect Implementation:

# WRONG: Starting from 0 unnecessarily in Phase 1
candidate = 0
for i in range(0, n):  # Should start from 1, not 0
    if knows(candidate, i):
        candidate = i

Why This Matters: Starting from 0 would make an unnecessary knows(0, 0) call and could potentially cause logic errors depending on how self-knowledge is defined in the problem.

Pitfall 4: Not Understanding the Optimization

The Problem: Some might try to "optimize" by breaking early or adding unnecessary conditions, not realizing the algorithm is already optimal.

Incorrect Attempt:

# WRONG: Trying to "optimize" with early termination
candidate = 0
found = False
for i in range(1, n):
    if knows(candidate, i):
        candidate = i
    else:
        found = True  # This doesn't mean we found a celebrity!
        break

Why This is Wrong: The Phase 1 loop MUST check all n-1 people to ensure we have the only possible candidate. Early termination would miss potential candidates.

Key Takeaway

The elegance of this solution lies in its simplicity: Phase 1 uses exactly n-1 queries to find the ONLY possible candidate, and Phase 2 verifies this candidate with at most 2(n-1) additional queries. Trying to "improve" this often leads to incorrect solutions or unnecessary complexity.