LeetCode 277 - Find the Celebrity

LeetCode Problem 277

Difficulty: 🟡 Medium
Topics: Two Pointers, Graph Theory, Interactive

Solution

Problem Understanding

This problem asks us to identify whether there is a "celebrity" among n people at a party. A celebrity has a very specific property:

• Every other person knows the celebrity.
• The celebrity knows nobody else.

We are not given the entire relationship graph directly. Instead, we can only query relationships through the helper API:

knows(a, b)

This function returns True if person a knows person b, otherwise False.

The goal is to implement:

findCelebrity(n)

which returns:

• the label of the celebrity if one exists
• -1 if no celebrity exists

The important detail is that this is an interactive-style problem. Even though the examples show a matrix representation, the actual solution must rely only on calls to knows.

The constraints are relatively small, with n <= 100, so even quadratic solutions are acceptable. However, the follow-up introduces a stricter requirement: can we solve the problem using at most 3 * n API calls? That strongly suggests there is a more efficient strategy than checking every pair exhaustively.

A naive implementation can easily make unnecessary calls. For example:

• Multiple people may appear celebrity-like at first.
• A candidate may fail only one condition.
• A person who knows someone else can never be a celebrity.
• A person unknown by even one individual cannot be a celebrity.

The problem guarantees:

• graph[i][i] == 1
• relationships are deterministic
• there is at most one celebrity

That final guarantee is important because it allows us to eliminate candidates aggressively.

Approaches

Brute Force Approach

The brute force solution checks every person individually to determine whether they satisfy the celebrity conditions.

For each person i:

1. Check whether i knows anyone else.
2. Check whether everyone else knows i.

If both conditions hold, then i is the celebrity.

This works because the definition of a celebrity is explicit and easy to verify directly. However, the downside is that for each candidate we may need to inspect relationships with every other person.

That leads to O(n^2) API calls.

Even though n <= 100 makes this acceptable computationally, it does not satisfy the follow-up requirement of minimizing API usage.

Key Insight for the Optimal Solution

The key observation is that a single knows(a, b) query can eliminate one person from celebrity consideration.

Consider two people:

• If a knows b, then a cannot be the celebrity.
• If a does not know b, then b cannot be the celebrity.

In either case, one candidate is eliminated.

This means we can identify a single potential celebrity in one linear pass.

We maintain a candidate variable:

• Start with person 0.
• Compare the current candidate with every other person.
• If the candidate knows someone, the candidate is disqualified and replaced.

After one pass, only one possible celebrity remains.

However, being the final candidate does not automatically guarantee celebrity status. We still must verify:

• the candidate knows nobody else
• everyone else knows the candidate

This leads to an O(n) solution overall.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every person against everyone else
Optimal	O(n)	O(1)	Eliminates non-celebrities in one pass, then verifies

Algorithm Walkthrough

Optimal Candidate Elimination Algorithm

1. Initialize a candidate variable to 0.

At the beginning, any person could theoretically be the celebrity. 2. Iterate through all people from 1 to n - 1.

For each person i, ask:

knows(candidate, i)

3. If the current candidate knows i, eliminate the candidate.

Since celebrities know nobody, the current candidate cannot be the celebrity anymore.

Update:

candidate = i

4. If the current candidate does not know i, eliminate i.

Since candidate does not know i, person i cannot be the celebrity because celebrities must be known by everyone. 5. After the first pass, exactly one possible celebrity remains.

This does not yet prove the candidate is valid. 6. Perform a verification pass.

For every other person i:

• If candidate knows i, return -1
• If i does not know candidate, return -1

7. If all checks pass, return the candidate.

Why it works

The elimination phase maintains an important invariant:

• After processing person i, every person before i except possibly the current candidate has already been eliminated.

Each comparison removes exactly one person from consideration. Since only one celebrity can exist, after n - 1 comparisons there can be at most one remaining candidate.

The verification phase ensures the candidate satisfies both celebrity properties exactly.

Python Solution

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

class Solution:
    def findCelebrity(self, n: int) -> int:
        candidate = 0

        # Step 1: Find a potential celebrity
        for person in range(1, n):
            if knows(candidate, person):
                candidate = person

        # Step 2: Verify the candidate
        for person in range(n):
            if person == candidate:
                continue

            # Celebrity should not know anyone
            if knows(candidate, person):
                return -1

            # Everyone should know the celebrity
            if not knows(person, candidate):
                return -1

        return candidate

The implementation follows the exact two-phase strategy described earlier.

The first loop performs candidate elimination. Every time the current candidate knows another person, the candidate is disqualified because celebrities know nobody. The new person becomes the only remaining possible celebrity among those examined so far.

After the first pass completes, we have only a potential celebrity. The second loop validates the candidate carefully.

The verification checks both celebrity conditions independently:

• the candidate must not know any other person
• every other person must know the candidate

If either condition fails even once, the function immediately returns -1.

Otherwise, the candidate is confirmed as the celebrity.

Go Solution

/**
 * The knows API is already defined for you.
 *     knows := func(a int, b int) bool
 */
func solution(knows func(a int, b int) bool) func(n int) int {
    return func(n int) int {
        candidate := 0

        // Step 1: Find a potential celebrity
        for person := 1; person < n; person++ {
            if knows(candidate, person) {
                candidate = person
            }
        }

        // Step 2: Verify the candidate
        for person := 0; person < n; person++ {
            if person == candidate {
                continue
            }

            // Celebrity should not know anyone
            if knows(candidate, person) {
                return -1
            }

            // Everyone should know the celebrity
            if !knows(person, candidate) {
                return -1
            }
        }

        return candidate
    }
}

The Go implementation is structurally identical to the Python version.

One small difference is that Go uses explicit variable declarations and loop syntax. Since all values fit comfortably within standard integer ranges, integer overflow is not a concern.

The solution uses constant extra space because only a few integer variables are maintained throughout execution.

Worked Examples

Example 1

Input:

graph = [
  [1,1,0],
  [0,1,0],
  [1,1,1]
]

Expected output:

1

Candidate Elimination Phase

Step	Candidate	Current Person	knows(candidate, person)	Action
Start	0	-	-	Initial candidate
1	0	1	True	Candidate becomes 1
2	1	2	False	Keep candidate 1

After elimination:

candidate = 1

Verification Phase

Check person 0:

Condition	Result
knows(1, 0)	False
knows(0, 1)	True

Check person 2:

Condition	Result
knows(1, 2)	False
knows(2, 1)	True

All checks pass.

Return:

1

Example 2

Input:

graph = [
  [1,0,1],
  [1,1,0],
  [0,1,1]
]

Expected output:

-1

Candidate Elimination Phase

Step	Candidate	Current Person	knows(candidate, person)	Action
Start	0	-	-	Initial candidate
1	0	1	False	Keep candidate 0
2	0	2	True	Candidate becomes 2

After elimination:

candidate = 2

Verification Phase

Check person 0:

Condition	Result
knows(2, 0)	False
knows(0, 2)	True

Check person 1:

Condition	Result
knows(2, 1)	True

Since the candidate knows another person, candidate 2 cannot be a celebrity.

Return:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to find candidate, one pass to verify
Space	O(1)	Only a few variables are used

The elimination phase performs exactly n - 1 comparisons. The verification phase performs at most 2 * (n - 1) additional checks.

Therefore, the total number of API calls is linear in n, which satisfies the follow-up constraint of staying within roughly 3 * n calls.

No auxiliary data structures are required, so the space complexity remains constant.

Test Cases

def find_celebrity_solver(graph):
    n = len(graph)

    def knows(a, b):
        return graph[a][b] == 1

    candidate = 0

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

    for person in range(n):
        if person == candidate:
            continue

        if knows(candidate, person):
            return -1

        if not knows(person, candidate):
            return -1

    return candidate

# Example 1, valid celebrity
graph = [
    [1, 1, 0],
    [0, 1, 0],
    [1, 1, 1]
]
assert find_celebrity_solver(graph) == 1

# Example 2, no celebrity exists
graph = [
    [1, 0, 1],
    [1, 1, 0],
    [0, 1, 1]
]
assert find_celebrity_solver(graph) == -1

# Smallest valid input with celebrity
graph = [
    [1, 1],
    [0, 1]
]
assert find_celebrity_solver(graph) == 1

# Smallest valid input without celebrity
graph = [
    [1, 1],
    [1, 1]
]
assert find_celebrity_solver(graph) == -1

# Celebrity is person 0
graph = [
    [1, 0, 0],
    [1, 1, 0],
    [1, 0, 1]
]
assert find_celebrity_solver(graph) == 0

# Celebrity is last person
graph = [
    [1, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 0, 1]
]
assert find_celebrity_solver(graph) == 3

# Candidate fails because one person does not know them
graph = [
    [1, 1, 0],
    [0, 1, 0],
    [1, 0, 1]
]
assert find_celebrity_solver(graph) == -1

# Candidate fails because they know someone
graph = [
    [1, 1, 0],
    [0, 1, 1],
    [1, 1, 1]
]
assert find_celebrity_solver(graph) == -1

Test Case Summary

Test	Why
Example 1	Validates standard celebrity detection
Example 2	Validates no celebrity scenario
Two people with celebrity	Tests smallest valid case
Two people without celebrity	Tests smallest invalid case
Celebrity at index 0	Ensures first person can be celebrity
Celebrity at last index	Ensures elimination logic works correctly
Missing incoming edge	Tests failed verification condition
Candidate knows someone	Tests second failed verification condition

Edge Cases

One important edge case occurs when there are only two people. In this situation, the algorithm must still correctly determine whether one person knows the other while remaining unknown themselves. Small inputs often expose off-by-one mistakes in loops or verification logic. The implementation handles this correctly because both the elimination and verification phases naturally scale down to size two without requiring special handling.

Another important edge case occurs when the final candidate is not actually a celebrity. The elimination phase guarantees only that all other candidates have been ruled out, not that the remaining candidate satisfies the celebrity conditions. A common bug is returning the candidate immediately after the first pass. The verification phase prevents this mistake by explicitly checking both celebrity properties.

A third important edge case happens when a candidate is known by everyone but also knows someone else. Such a person is popular but not a celebrity according to the problem definition. The implementation correctly rejects this case during verification through the condition:

if knows(candidate, person):
    return -1

Another subtle case occurs when nobody qualifies because at least one person does not know the candidate. Even if the candidate knows nobody, they still fail the celebrity definition if someone does not recognize them. The second verification condition ensures this scenario is handled correctly.