Code Implementation

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

class Solution:
    def findCelebrity(self, n: int) -> int:
        # Step 1: Find the candidate
        candidate = 0
        for i in range(1, n):
            if knows(candidate, i):
                candidate = i
        
        # Step 2: Validate the candidate
        for i in range(n):
            if i != candidate:
                if knows(candidate, i) or not knows(i, candidate):
                    return -1
        return candidate
      

// The knows API is defined for you.
// bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; ++i) {
            if (knows(candidate, i))
                candidate = i;
        }
        for (int i = 0; i < n; ++i) {
            if (i != candidate) {
                if (knows(candidate, i) || !knows(i, candidate))
                    return -1;
            }
        }
        return candidate;
    }
};
      

/* The knows API is defined in the parent class Relation.
   boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) {
                candidate = i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i != candidate) {
                if (knows(candidate, i) || !knows(i, candidate)) {
                    return -1;
                }
            }
        }
        return candidate;
    }
}
      

/**
 * // The knows API is defined for you.
 * var knows = function(personA, personB) {
 *     ...
 * };
 */

/**
 * @param {number} n
 * @return {number}
 */
var findCelebrity = function(n) {
    let candidate = 0;
    for (let i = 1; i < n; i++) {
        if (knows(candidate, i)) {
            candidate = i;
        }
    }
    for (let i = 0; i < n; i++) {
        if (i !== candidate) {
            if (knows(candidate, i) || !knows(i, candidate)) {
                return -1;
            }
        }
    }
    return candidate;
};
      

Problem Description

You are at a party with n people labeled from 0 to n - 1. Some people know each other, and some do not. A celebrity is defined as someone who:

• Is known by everyone else at the party
• Does not know anyone else (except possibly themselves)

• There is at most one celebrity at the party.
• You must minimize the number of calls to knows.

Thought Process

At first glance, it might seem that we need to check every pair of people to see who knows whom, which would take a lot of time. For each person, we could check if everyone knows them and if they know no one else. But this would require O(n^2) calls to knows, which is inefficient.

Instead, we can realize that if person A knows person B, then A cannot be the celebrity (since celebrities know no one). Likewise, if A does not know B, then B cannot be the celebrity (since everyone must know the celebrity).

This insight allows us to efficiently eliminate non-celebrities and narrow down to a single potential candidate, then verify that candidate.

Solution Approach

• Step 1: Candidate Selection
  • Start with the first person (label 0) as the celebrity candidate.
  • Iterate through each person i from 1 to n-1:
  • If the current candidate knows i, then the candidate cannot be the celebrity (since celebrities know no one). So, set i as the new candidate.
  • If the candidate does not know i, keep the current candidate.
• Step 2: Candidate Verification
  • After the loop, you have one candidate who could potentially be the celebrity.
  • For every other person j (where j != candidate):
  • Check that the candidate does not know j (knows(candidate, j) == False).
  • Check that j knows the candidate (knows(j, candidate) == True).
  • If either check fails, return -1 (no celebrity).
• Step 3: Return the Result
  • If the candidate passes all checks, return their label as the celebrity.

This approach reduces the number of knows calls to O(n), which is much more efficient than the brute-force method.

Example Walkthrough

Suppose n = 4 and the following "knows" relationships exist:

• Person 0 knows 1 and 3
• Person 1 knows 3
• Person 2 knows 3
• Person 3 knows no one

• Start with candidate = 0
• Does 0 know 1? Yes → candidate = 1
• Does 1 know 2? No → candidate stays 1
• Does 1 know 3? Yes → candidate = 3

• Check each person except 3:
• Does 3 know 0? No (good)
• Does 0 know 3? Yes (good)
• Does 3 know 1? No (good)
• Does 1 know 3? Yes (good)
• Does 3 know 2? No (good)
• Does 2 know 3? Yes (good)

• Person 3 is the celebrity because everyone knows them and they know no one.

Time and Space Complexity

• Brute-force approach:
  • For each person, check if everyone knows them and they know no one else.
  • This requires O(n^2) calls to knows (since you check every pair).
• Optimized approach (above):
  • Candidate selection: O(n) calls (one for each person).
  • Verification: O(n) calls (one for each person, except the candidate).
  • Total: O(n) calls to knows.
  • Space complexity: O(1) extra space (only a few variables are used).

Summary

The "Find the Celebrity" problem uses a clever elimination process to efficiently identify the celebrity (if one exists) with only O(n) calls to the knows API. By iteratively narrowing down the candidate and then verifying just one person, we avoid the need to check every possible pair. This approach is both simple and elegant, making the most out of the problem's constraints and requirements.