Find The Celebrity - Leetcode Solution

The "Find The Celebrity" problem on LeetCode is a well-known problem in computer science. It is a simple problem that requires a basic understanding of matrices and graph theory.

Problem Statement:

Suppose you are at a party with n people (labeled 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 him/her, but he/she does not know any of them.

You are given a matrix called 'knows' that represents the relation of people knowing each other.

If 'knows[i][j] = 1', then person i knows person j. If 'knows[i][j] = 0', then person i does not know person j.

Write a function to find the celebrity, if one exists. Otherwise, return -1.

Note:

• There will be exactly one celebrity if he/she is present in the party. Return the celebrity's label if he/she is present, otherwise, return -1.

• You must write an API 'bool knows(int a, int b)' which tells you whether A knows B. Implement it however you want.

• You are not allowed to use any extra space. Ex: dict, set, list, etc.

Solution:

The first step in solving this problem is to understand the definition of a celebrity. A celebrity is a person who is known by everyone but does not know anyone. In other words, a celebrity is a node in the graph with no outgoing edges and n-1 incoming edges.

To find the celebrity, we can start by iterating through all the people and finding a candidate. We can do this by selecting the first person as a candidate and then iterating through all other people to check if this candidate knows any other person. If the candidate knows someone, we can update the candidate to the person he/she knows.

As we iterate through all people, we continuously update the candidate. Once we have checked all people, there is only one person left, which is our candidate celebrity.

However, we have not yet checked if this candidate is a celebrity. To check if the candidate is a celebrity, we need to iterate through all people again and check:

• If the candidate knows any other person
• If any other person does not know the candidate.

If the candidate does not know anyone and everyone knows the candidate, then the candidate is a celebrity.

If we find a person who does not know the candidate, we can immediately return -1 since this person cannot be the celebrity.

Let's implement this algorithm in Python:

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: Verify if the candidate is a celebrity
        for i in range(n):
            if i == candidate:
                continue
                
            if knows(candidate, i) or not knows(i, candidate):
                return -1
        
        return candidate

In this solution, we first find the candidate celebrity, and then we verify if the candidate is a celebrity by checking if he/she knows anyone and if everyone knows the candidate.

This solution has a time complexity of O(n) since we are iterating through all people only twice. It also uses constant space since we are not using any extra space. Therefore, this solution satisfies the problem constraints.

1