Leetcode 277. Find the Celebrity

Problem

You are organizing an exclusive event with n guests numbered from 0 to n-1. Among these guests, there might be exactly one VIP guest who has a very specific characteristic:

• The VIP knows no other guests at the event
• Every other guest knows the VIP

You have access to a pre-defined API function knows(a, b) that returns true if person a knows person b, and false otherwise. This API call counts as one query.

Your task is to identify the VIP guest if one exists, or return -1 if no such person exists. The challenge is to minimize the number of API calls you make.

Requirements

1. Implement a function that takes the number of guests n and returns the index of the VIP or -1
2. Use the provided knows(a, b) API to query relationships
3. Handle the case where no VIP exists
4. Optimize your solution to use as few API calls as possible
5. The VIP must know zero people and be known by all n-1 others

Constraints

• 1 ≤ n ≤ 1000
• At most one VIP exists
• Time complexity should be O(n)
• Space complexity should be O(1)
• Minimize the number of knows() API calls

Examples

Example 1:

` Input: n = 3 Relationships:

• knows(0, 1) = true
• knows(0, 2) = false
• knows(1, 0) = false
• knows(1, 2) = false
• knows(2, 0) = true
• knows(2, 1) = true Output: 1 Explanation: Person 1 knows nobody (knows(1,0)=false, knows(1,2)=false), and both person 0 and person 2 know person 1 (knows(0,1)=true, knows(2,1)=true). `

Example 2:

` Input: n = 2 Relationships:

• knows(0, 1) = true
• knows(1, 0) = true Output: -1 Explanation: Both people know each other, so neither can be the VIP. `

Example 3:

Input: n = 1 Output: 0 Explanation: With only one person, they are automatically the VIP (knows nobody and everyone knows them vacuously).

Hint 1: Candidate Elimination When comparing two people A and B, if A knows B, then A cannot be the VIP. If A doesn't know B, then B cannot be the VIP. Use this logic to eliminate n-1 candidates with just n-1 comparisons.

Hint 2: Two-Phase Approach First, find a candidate by eliminating all but one person. Then, verify that this candidate truly satisfies both VIP conditions: they know nobody, and everyone knows them.

Hint 3: Linear Scan Start with person 0 as the candidate. For each subsequent person i, if the candidate knows i, update the candidate to i. After this pass, verify the final candidate in a second pass.

Full Solution `` Solution Explanation:

The algorithm works in two phases:

Phase 1 - Candidate Elimination (O(n)):

• We use the key insight that in any comparison between two people, we can eliminate one as a potential VIP
• If person A knows person B, then A cannot be the VIP (VIP knows nobody)
• If person A doesn't know person B, then B cannot be the VIP (everyone must know the VIP)
• We iterate through all n people, maintaining a candidate and eliminating n-1 people
• This takes exactly n-1 knows() calls

Phase 2 - Verification (O(n)):

• After finding a candidate, we must verify they satisfy both conditions
• First, check that the candidate knows nobody: iterate through all n people and confirm knows(candidate, i) is false for all i ≠ candidate
• Second, check that everyone knows the candidate: iterate through all n people and confirm knows(i, candidate) is true for all i ≠ candidate
• This takes at most 2(n-1) additional knows() calls

Time Complexity: O(n) - We make at most 3n API calls Space Complexity: O(1) - We only use a constant amount of extra space

The elegance of this solution lies in the elimination phase, where each comparison definitively rules out one person, guaranteeing we end with a valid candidate if a VIP exists.

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

def findVIP(n: int) -> int:
    # Phase 1: Find a candidate using elimination
    # Start with person 0 as the initial candidate
    candidate = 0
    
    # For each person from 1 to n-1, check if candidate knows them
    for i in range(1, n):
        if knows(candidate, i):
            # If candidate knows person i, candidate cannot be VIP
            # Update candidate to person i
            candidate = i
        # If candidate doesn't know i, then i cannot be VIP
        # Keep current candidate and continue
    
    # Phase 2: Verify the candidate
    # The candidate must know nobody
    for i in range(n):
        if i != candidate and knows(candidate, i):
            return -1  # Candidate knows someone, not a VIP
    
    # Everyone else must know the candidate
    for i in range(n):
        if i != candidate and not knows(i, candidate):
            return -1  # Someone doesn't know candidate, not a VIP
    
    return candidate