NUHMAN.com

Introduction

LeetCode 277: Find the Celebrity is a well-known graph-based logic problem that tests your ability to eliminate possibilities efficiently.

Imagine you're at a party of n people. One of them might be a celebrity — someone who is:

1. Known by everyone else
2. Knows no one in return

Your task is to figure out who the celebrity is with the minimum number of "knows" API calls.

Problem Statement

Suppose you have n people labeled from 0 to n - 1, and a helper function knows(a, b) which returns True if person a knows person b.

Find the celebrity if one exists. Otherwise, return -1.

Examples

python

Input: knows(a, b) = True/False for all a, b
Output: 2

Explanation:
- Everyone knows person 2.
- Person 2 knows nobody.
- So, person 2 is the celebrity.

✅ Step-by-Step Solution

🧠 Key Observations

For someone c to be a celebrity:

• knows(c, anyone) should return False
• knows(anyone, c) should return True, except c themself

So if A knows B, A cannot be the celebrity, but B might be.

🔁 Step 1: Candidate Selection (Single Pass)

Loop through 0 to n-1 and find a candidate:

python

for i in range(n):
    if knows(candidate, i):
        candidate = i

At the end of this loop, candidate is the only possible celebrity.

🔁 Step 2: Validation

Now confirm this person is actually a celebrity:

python

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

✅ Python Code

python

# The knows API is already defined for you.
# def knows(a: int, b: int) -> bool:

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

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

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(1)Number of API CallsAt most 3(n−1)

Far more efficient than checking every pair (which would be O(n²))

🧪 Dry Run (n = 4)

Say knows(a, b) returns:

a \ b01230FTTF1FFTF2FFFF3TTTF

• candidate = 0 → 1 → 2 (0 knows 1, 1 knows 2)
• Validate 2: doesn't know anyone, everyone knows 2 → ✅ Celebrity!

🔍 Edge Cases

• n = 0 or 1 → Return -1 or 0 accordingly
• No celebrity exists → All fail the validation loop

✅ Conclusion

LeetCode 277: Find the Celebrity is a fantastic interview question for:

• Deductive reasoning
• Optimizing API-based queries
• Graph traversal logic