277. Find the Celebrity

Problem Statement

link: LeetCode.cn LeetCode Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. You are only allowed to ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) that tells you whether a knows b. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.

Return the celebrity’s label if there is a celebrity at the party. If there is no celebrity, return -1. Example:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]] Output: 1

Input: graph = [[1,0,1],[1,1,0],[0,1,1]] Output: -1

Constraints: n == graph.length == graph[i].length 2 <= n <= 100 graph[i][j] is 0 or 1. graph[i][i] == 1

Follow up: If the maximum number of allowed calls to the API knows is 3 * n, could you find a solution without exceeding the maximum number of calls?

Solution Approach

The solution iteratively selects a candidate by eliminating those who know others, then verifies the candidate by ensuring they are known by everyone but know no one in return.

Algorithm

1. Candidate Selection: Start with the first person as the candidate and iterate through the rest, updating the candidate if they know the current person, as the celebrity should not know anyone.
2. Candidate Validation: After identifying the candidate, verify if this person is indeed the celebrity by checking that they do not know anyone else and that everyone else knows them.
3. Return Result: If the candidate passes the validation checks, return their label as the celebrity; otherwise, return -1, indicating that no celebrity exists.

Implement

    class Solution: def findCelebrity(self, n: int) -> int:
    candidate = 0
    for x in range(1, n):
        if knows(candidate, x) == True:
            candidate = x
    for x in range(n):
        if candidate == x:
            continue
        if knows(candidate, x) == True:
            return -1
        if knows(x, candidate) == False:
            return -1
    return candidate


   
     

    
    

Twitter  facebook  Email