277. Find the Celebrity
Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 44.0%
Problem Breakdown
We need to identify one person out of n who satisfies two strict conditions: everyone else knows them (knows(i, celebrity) == True) and they know no one else (knows(celebrity, i) == False). We are restricted from accessing a direct adjacency matrix; we can only query relationships via the boolean API knows(a, b).
Inputs:
- An integer
nrepresenting the number of people (0 to n-1). - A helper function
bool knows(a, b)accessible in scope.
Outputs:
- The index label of the celebrity if one exists.
-1otherwise.
Implicit Constraints & Edge Cases:
- Uniqueness: There is at most one celebrity (or none). If there are two candidates satisfying partial conditions, they cannot both be celebrities because a celebrity must not know anyone else; thus, mutual knowledge between A and B disqualifies both immediately if we assume strict definition. However, the problem guarantees exactly zero or one celebrity exists in valid inputs for this specific LeetCode variant (though logically multiple could exist without constraints).
- Self-Knowledge:
graph[i][i] == 1is given as a constraint, but since celebrities don’t know others, self-knowledge doesn’t disqualify them. We must ignore the diagonal when checking relationships.
Intuition
A brute-force approach would check every person to see if they satisfy the celebrity conditions against everyone else. For each candidate i, we’d call knows for all other n-1 people twice (once as A, once as B). This results in roughly calls to knows. Given that knows is an expensive API operation (often simulated with a matrix lookup but restricted by count), we want asymptotic efficiency.
Key Insight:
If person A knows person B (knows(A, B) == True), then A cannot be the celebrity. Why? Because a celebrity must not know anyone else. Therefore, if knows(A, B) is true, A is disqualified immediately. We can discard A and promote B as our new potential candidate for being the celebrity (since we don’t yet know about B’s relationships with others).
This allows us to maintain only one current candidate at any time. As we iterate through everyone else:
- If
knows(candidate, i)is True -> Candidate knows someone -> Eliminate candidate, set new candidate =i. - If
knows(candidate, i)is False -> Candidate doesn’t know anyone yet (good) -> Keep current candidate as potential celebrity.
This elimination process reduces the pool of candidates to a single survivor in calls. Once we have one survivor, we must verify them against everyone else to ensure they meet both conditions fully. This verification step takes another pass. Total complexity becomes linear relative to n.
Approach
- Elimination Phase: Initialize our potential candidate (e.g., start with person
0or iterate through the list). Iterate from indexi = 1ton-1. Compare currentcandidateagainsti. If they know each other, swap them (candidate = i). This ensures we never keep a disqualified person. - Verification Phase: After iterating all people, one candidate remains (or none if logic handles it). We must verify this specific candidate satisfies the definition:
- For every
jfrom0ton-1:- If
candidate == j, skip. - Check that
knows(j, candidate)is True (everyone knows them). - Check that
knows(candidate, j)is False (they know no one else).
- If
- If any check fails, return
-1. Otherwise, return the index.
- For every
This approach guarantees at most calls to knows ( for elimination + verification), satisfying the follow-up constraint.
Complexity Analysis
- Time Complexity: . We iterate through people once during elimination and potentially verify them in a second pass (or combined). The number of operations is linear with respect to
n. - Space Complexity: . We only store the index of one candidate. No auxiliary data structures like stacks or arrays are needed beyond input variables.
Solution
def findCelebrity(n):
# Elimination Phase: Find a potential celebrity candidate
# Start with person 0 as our current best guess (or n-1)
candidate = 0
for i in range(1, n):
if knows(candidate, i):
# If 'candidate' knows 'i', then 'candidate' cannot be the celebrity.
# We discard 'candidate' and make 'i' our new potential candidate.
candidate = i
# Verification Phase: Check if the remaining candidate is actually a celebrity
for j in range(n):
if j == candidate:
continue
# A celebrity must be known by everyone else (knows(j, candidate) == True)
# AND they must not know anyone else (knows(candidate, j) == False).
if knows(candidate, j) or not knows(j, candidate):
return -1
return candidate
# Note: In a LeetCode environment, 'knows' is provided as an instance method
# accessible within the class scope. For this standalone function walkthrough,
# we assume it exists in the global scope or passed via closure.
Edge Cases Handled
- No Celebrity Exists: The verification loop will fail if any condition (everyone knows them / they know no one) is violated for the survivor from elimination, correctly returning
-1. - Single Person (
n=2): Logic holds; loops run once or zero times depending on range. Ifknows(0, 1)exists, candidate becomes 1. Verification checks if 0 knows 1 (should be false) and 1 known by 0 (true). - Self-Reference: The code explicitly skips checking the diagonal (
if j == candidate: continue), adhering tograph[i][i] == 1constraint without treating self-knowledge as a disqualifier.