1. Brute Force

Intuition

A celebrity is someone who is known by everyone but knows nobody. For each person, we can check if they satisfy both conditions: they don't know anyone else, and everyone else knows them. If both conditions hold, that person is the celebrity.

Algorithm

1. For each person i from 0 to n-1:
   • Check if i is a celebrity by verifying two conditions for every other person j:
     • i does not know j.
     • j knows i.
   • If both conditions hold for all j, return i.
2. If no celebrity is found, return -1.

class Solution:
    def findCelebrity(self, n: int) -> int:
        self.n = n
        for i in range(n):
            if self.is_celebrity(i):
                return i
        return -1
    
    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue # Don't ask if they know themselves.
            if knows(i, j) or not knows(j, i):
                return False
        return True

Time & Space Complexity

We don't know what time and space the knows(...) API uses. Because it's not our concern, we'll assume it's O(1) for the purpose of analysing our algorithm.

• Time complexity: $O(n^2)$
• Space complexity: $O(1)$

Where $n$ is the number of nodes in the graph.

---

2. Logical Deduction

Intuition

Each knows(a, b) call eliminates one person from being a celebrity. If a knows b, then a cannot be the celebrity (celebrities know nobody). If a doesn't know b, then b cannot be the celebrity (everyone must know the celebrity). By iterating through all people once, we can narrow down to a single candidate. We then verify this candidate with a second pass.

Algorithm

1. Start with candidate = 0.
2. For each person i from 1 to n-1:
   • If candidate knows i, update candidate = i (previous candidate is disqualified).
3. Verify the candidate by checking:
   • The candidate knows nobody.
   • Everyone knows the candidate.
4. Return the candidate if valid, otherwise return -1.

class Solution:
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if knows(celebrity_candidate, i):
                celebrity_candidate = i
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if knows(i, j) or not knows(j, i):
                return False
        return True

Time & Space Complexity

We don't know what time and space the knows(...) API uses. Because it's not our concern, we'll assume it's O(1) for the purpose of analysing our algorithm.

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Where $n$ is the number of nodes in the graph.

---

3. Logical Deduction with Caching

Intuition

The logical deduction approach may call knows(a, b) multiple times with the same arguments during the verification phase. By caching the results of each call, we can avoid redundant API calls. This is particularly useful when the knows function is expensive to evaluate.

Algorithm

1. Create a cache to store results of knows(a, b) calls.
2. Use the same logical deduction approach to find the candidate.
3. During verification, check the cache before calling knows.
4. Return the candidate if valid, otherwise return -1.

from functools import lru_cache

class Solution:
    
    @lru_cache(maxsize=None)
    def cachedKnows(self, a, b):
        return knows(a, b)
    
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if self.cachedKnows(celebrity_candidate, i):
                celebrity_candidate = i
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if self.cachedKnows(i, j) or not self.cachedKnows(j, i):
                return False
        return True

Time & Space Complexity

We don't know what time and space the knows(...) API uses. Because it's not our concern, we'll assume it's O(1) for the purpose of analysing our algorithm.

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the number of nodes in the graph.

---

Common Pitfalls

Skipping the Verification Step

After finding a candidate using logical deduction, you must verify that the candidate truly knows nobody and is known by everyone. The candidate elimination only guarantees the candidate could be a celebrity, not that they definitely are one. Skipping verification can return false positives.

Starting the Candidate Search from Wrong Index

In the logical deduction approach, starting from candidate 0 and iterating from index 1 is intentional. Starting the loop from index 0 with knows(candidate, 0) would incorrectly update the candidate when comparing a person to themselves, since knows(0, 0) might return true.

Calling knows(i, i) During Verification

When verifying the candidate, always skip the case where i == j. Asking if someone knows themselves is undefined behavior in this problem and could return unexpected results that break your verification logic.