Practice/LinkedIn/Leetcode 277. Find the Celebrity

Leetcode 277. Find the Celebrity

CodingMust

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).