Find the Celebrity

XXX. Find the Celebrity

Graph

Logical Deduction

Problem Statement:

In a party of n people, find the celebrity. A celebrity is defined as someone who:

• Doesn't know anyone at the party
• Everyone else knows the celebrity
• You have access to knows(a, b) API which returns if a knows b
• Return -1 if there is no celebrity

Algorithm:

1. **First Pass**:
   • Identify possible celebrity candidate
   • If A knows B, A cannot be celebrity
   • If A doesn't know B, B cannot be celebrity
2. **Second Pass**:
   • Verify candidate knows no one
   • Verify everyone knows candidate
   • Return -1 if verification fails

Complexity:

Time Complexity: O(n), requires two passes through array
Space Complexity: O(1), only uses constant extra space

Implementation:

Java Solution:

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int possibleCeleb = 0;                     // Start with first person
        
        // First pass: Eliminate non-celebrities
        for (int i = 1; i < n; i++)
            if (knows(possibleCeleb, i))           // If A knows B, A can't be celeb
                possibleCeleb = i;
        
        // Second pass: Verify the candidate
        for (int i = 0; i < n; i++) {
            if (i == possibleCeleb) continue;
            if (!knows(i, possibleCeleb)) return -1;  // Everyone must know celeb
            if (knows(possibleCeleb, i)) return -1;   // Celeb must know no one
        }
        
        return possibleCeleb;
    }
}
                

Python Solution:

class Solution(Relation):
    def findCelebrity(self, n: int) -> int:
        possible_celeb = 0                         # Start with first person
        
        # First pass: Eliminate non-celebrities
        for i in range(1, n):
            if self.knows(possible_celeb, i):      # If A knows B, A can't be celeb
                possible_celeb = i
        
        # Second pass: Verify the candidate
        for i in range(n):
            if i == possible_celeb:
                continue
            if not self.knows(i, possible_celeb):  # Everyone must know celeb
                return -1
            if self.knows(possible_celeb, i):      # Celeb must know no one
                return -1
        
        return possible_celeb
                

C++ Solution:

class Solution : public Relation {
public:
    int findCelebrity(int n) {
        int possibleCeleb = 0;                     // Start with first person
        
        // First pass: Eliminate non-celebrities
        for (int i = 1; i < n; i++)
            if (knows(possibleCeleb, i))           // If A knows B, A can't be celeb
                possibleCeleb = i;
        
        // Second pass: Verify the candidate
        for (int i = 0; i < n; i++) {
            if (i == possibleCeleb) continue;
            if (!knows(i, possibleCeleb)) return -1;  // Everyone must know celeb
            if (knows(possibleCeleb, i)) return -1;   // Celeb must know no one
        }
        
        return possibleCeleb;
    }
};
                

Explanation:

• **First Pass Logic**:
  • If A knows B, A cannot be celebrity (celebrities know no one)
  • B becomes new candidate
  • Efficiently eliminates non-celebrities
• **Verification Process**:
  • Check if candidate knows anyone (should not)
  • Check if everyone knows candidate (should)
  • Both conditions must be true for valid celebrity
• **Key Insights**:
  • Only need two passes through array
  • First pass guarantees all people after candidate cannot be celebrity
  • Second pass verifies candidate meets all conditions