Find the Celebrity

How it works

Each knows(a, b) call eliminates one person from being a celebrity. If a knows b, then a cannot be the celebrity (celebrities know nobody). If a doesn't know b, then b cannot be the celebrity (everyone must know the celebrity). By iterating through all people once, we can narrow down to a single candidate. We then verify this candidate with a second pass.

Steps

1. Start with candidate = 0.
2. For each person i from 1 to n-1:
   • If candidate knows i, update candidate = i (previous candidate is disqualified).
3. Verify the candidate by checking:
   • The candidate knows nobody.
   • Everyone knows the candidate.
4. Return the candidate if valid, otherwise return -1.

Complexity

We don't know what time and space the knows(...) API uses. Because it's not our concern, we'll assume it's O(1) for the purpose of analysing our algorithm.

• Time complexity: O(n)
• Space complexity: O(1)

Where n is the number of nodes in the graph.

Things to watch for

Skipping the Verification Step

After finding a candidate using logical deduction, you must verify that the candidate truly knows nobody and is known by everyone. The candidate elimination only guarantees the candidate could be a celebrity, not that they definitely are one. Skipping verification can return false positives.

Starting the Candidate Search from Wrong Index

In the logical deduction approach, starting from candidate 0 and iterating from index 1 is intentional. Starting the loop from index 0 with knows(candidate, 0) would incorrectly update the candidate when comparing a person to themselves, since knows(0, 0) might return true.

Calling knows(i, i) During Verification

When verifying the candidate, always skip the case where i == j. Asking if someone knows themselves is undefined behavior in this problem and could return unexpected results that break your verification logic.

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

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if knows(i, j) or not knows(j, i):
                return False
        return True

class Solution {
private:
    int n;
    
    bool is_celebrity(int i) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (knows(i, j) || !knows(j, i)) {
                return false;
            }
        }
        return true;
    }
    
public:
    int findCelebrity(int n) {
        this->n = n;
        int celebrity_candidate = 0;
        
        for (int i = 1; i < n; i++) {
            if (knows(celebrity_candidate, i)) {
                celebrity_candidate = i;
            }
        }
        
        if (is_celebrity(celebrity_candidate)) {
            return celebrity_candidate;
        }
        return -1;
    }
};