Watch 10 video solutions for Find the Celebrity, a medium level problem involving Two Pointers, Graph, Interactive. This walkthrough by take U forward has 57,215 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Overview: You are given n people at a party and access to a function knows(a, b) that tells whether person a knows person b. A celebrity is someone who is known by everyone else but knows no one. Your task is to determine the celebrity index or return -1 if no such person exists.
Approach 1: Brute Force Using In/Out Degree (O(n²) time, O(n) space)
Treat the party as a directed graph where an edge a → b exists if a knows b. A celebrity must have outdegree = 0 and indegree = n-1. Iterate through every pair of people and update two arrays tracking incoming and outgoing edges. After processing all relationships, scan for a person whose indegree is n-1 and outdegree is 0. This method clearly models the problem using a graph perspective but requires checking all pairs, which makes it inefficient for large n.
Approach 2: Candidate Elimination (Two Pointers) (O(n) time, O(1) space)
The key observation: if a knows b, then a cannot be the celebrity. If a does not know b, then b cannot be the celebrity. Use two pointers starting at both ends of the group. Compare people and eliminate one candidate at each step until only one possible celebrity remains. This linear elimination works because every comparison removes exactly one invalid candidate. The technique is closely related to two pointers and drastically reduces the search space.
Approach 3: Candidate Verification (O(n) time, O(1) space)
The elimination step only produces a potential celebrity. A final pass must verify the candidate. Iterate through all other people and check two conditions: the candidate must not know anyone, and everyone must know the candidate. If either condition fails, return -1. This verification step is necessary because the elimination logic guarantees only that other candidates are invalid, not that the remaining person actually satisfies both celebrity properties.
The problem is also categorized as an interactive style question because you cannot directly inspect the relationship matrix; you must query it through the knows() API.
Recommended for interviews: Interviewers expect the O(n) candidate elimination approach followed by verification. The brute force graph-style solution demonstrates correct reasoning about indegree and outdegree, but the optimal linear scan shows stronger algorithmic insight and efficient API usage.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph In/Out Degree Counting | O(n²) | O(n) | Useful for understanding the problem as a directed graph and validating celebrity conditions explicitly |
| Two Pointer Candidate Elimination | O(n) | O(1) | Best general solution; eliminates one candidate per comparison |
| Candidate Verification Pass | O(n) | O(1) | Required final step to confirm the remaining candidate actually satisfies celebrity rules |
