Find the Celebrity

Medium

TikTok

0 views

Topics:

Arrays

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 him/her but he/she does not know any of them.

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

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int celebrity(n) that returns the celebrity's label if the celebrity is present at the party. If there is no celebrity, return -1.

Note: The relation is transitive. That is, if A knows B and B knows C, then A knows C.

You will not have direct access to the knowledge of relationships between people. The judge will use your implementation to assess your algorithm.

Example 1:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three people labeled 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is person 1 because everyone except him knows him and he knows no one.

Example 2:

Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

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

Follow up: Minimize the number of calls to knows.

Find the Celebrity

Medium

TikTok

0 views

Topics:

Arrays

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 him/her but he/she does not know any of them.

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

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int celebrity(n) that returns the celebrity's label if the celebrity is present at the party. If there is no celebrity, return -1.

Note: The relation is transitive. That is, if A knows B and B knows C, then A knows C.

You will not have direct access to the knowledge of relationships between people. The judge will use your implementation to assess your algorithm.

Example 1:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three people labeled 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is person 1 because everyone except him knows him and he knows no one.

Example 2:

Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

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

Follow up: Minimize the number of calls to knows.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n`, the number of people? Is `n` guaranteed to be non-negative?
If there are multiple people who are known by everyone else and don't know anyone, or if there are inconsistencies in the `knows` matrix such that no celebrity exists, what value should I return?
Can I assume that the `knows` matrix is a valid square matrix of size `n x n`? Will I need to handle cases where the matrix is not square or is null/empty?
Is it possible for a person to know themselves (i.e., `knows(i, i)` can be true)?
Can you please clarify the behavior of `knows(a,b)` when a or b are out of range (e.g., negative or greater than or equal to n)? If the function is guaranteed to only be called with valid indices, I will not handle this.

Brute Force Solution

Approach

The brute force approach to finding a celebrity involves checking every single person to see if they fit the celebrity criteria. We essentially test each person's celebrity status individually by examining their relationships with everyone else. This means exhaustively comparing each person against all other people to see if they are known by everyone and know no one else.

Here's how the algorithm would work step-by-step:

Consider the first person as a potential celebrity.
Check if everyone else knows this person.
Also, check if this person knows anyone else.
If everyone knows this person, and this person knows no one else, then we've found a celebrity!
If not, then repeat the process for the second person.
Continue doing this for every single person until a celebrity is found, or until you've checked everyone.

Code Implementation

def find_celebrity_brute_force(number_of_people):
    for potential_celebrity in range(number_of_people):

        everyone_knows_potential_celebrity = True
        potential_celebrity_knows_no_one = True

        # Check if everyone knows the potential celebrity.
        for other_person in range(number_of_people):
            if other_person != potential_celebrity and not knows(other_person, potential_celebrity):
                everyone_knows_potential_celebrity = False
                break

        # Check if the potential celebrity knows anyone.
        if everyone_knows_potential_celebrity:
            for other_person in range(number_of_people):
                if other_person != potential_celebrity and knows(potential_celebrity, other_person):
                    potential_celebrity_knows_no_one = False
                    break

            # If both conditions are true, we found a celebrity.
            if potential_celebrity_knows_no_one:
                return potential_celebrity

    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n people to determine if they are the celebrity. For each person, the algorithm checks if everyone else knows them, which requires up to n-1 comparisons. Additionally, for each person, the algorithm verifies that they know no one else, which again requires up to n-1 comparisons. Thus, for each of the n people, we perform up to 2*(n-1) comparisons. The total number of operations approximates n * (2n - 2), simplifying to 2n² - 2n. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm checks each person's celebrity status individually without using any auxiliary data structures. It only involves checking boolean conditions (knows or doesn't know), and implicitly the plain English explanation suggests iterating through individuals one by one. Therefore, it only uses a constant amount of extra space, regardless of the number of people (N) involved, as it doesn't require any lists, maps, or other data structures to store intermediate results or track visited nodes. The space complexity is thus O(1).

Optimal Solution

Approach

The problem is like finding a famous person in a group. We can efficiently identify this person by strategically eliminating candidates based on pairwise relationships, eventually narrowing down to a single potential celebrity. Then we confirm that person truly meets the celebrity criteria.

Here's how the algorithm would work step-by-step:

Start by picking any two people in the group.
Ask them whether they know each other. If the first person knows the second person, then the first person cannot be the celebrity, so eliminate the first person.
Otherwise, if the first person doesn't know the second person, then the second person cannot be the celebrity, so eliminate the second person.
Repeat this process of picking two people (one of whom is the latest remaining person) and eliminating one of them until only one person remains.
Now that we have a potential celebrity, we must verify they are actually a celebrity.
Check if everyone else knows this potential celebrity. If anyone doesn't, then this person is not a celebrity.
Check if this potential celebrity knows anyone else. If they do, then this person is not a celebrity.
If the person is known by everyone else and doesn't know anyone else, they are the celebrity.

Code Implementation

def find_celebrity(number_of_people):
    potential_celebrity = 0
    for i in range(1, number_of_people):
        if knows(potential_celebrity, i):

            #Eliminate potential celebrity, i is new candidate
            potential_celebrity = i

    # Verify the potential celebrity
    for i in range(number_of_people):

        # Check if anyone doesn't know potential celebrity
        if i != potential_celebrity and not knows(i, potential_celebrity):
            return -1

        # Check if the potential celebrity knows anyone
        if i != potential_celebrity and knows(potential_celebrity, i):
            return -1

    return potential_celebrity

def knows(person_a, person_b):
    #Placeholder function, replace with actual implementation
    pass

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The initial phase reduces the potential celebrity candidates to one using pairwise comparisons via the knows(a, b) API. This phase iterates at most n-1 times, resulting in O(n) calls to the knows API. The verification phase checks if the potential celebrity is known by everyone else (n-1 calls to knows) and doesn't know anyone else (n-1 calls to knows), also taking O(n) time. Therefore, the overall time complexity is O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store indices and potentially a final candidate. The space required for these variables does not depend on the input size N (the number of people). No auxiliary data structures like arrays or hash maps are used to store intermediate results, meaning the auxiliary space remains constant regardless of the input size.

Edge Cases

Case	How to Handle
Null or empty knows matrix (n=0)	Return -1 immediately as there are no people to check.
Single person (n=1)	If knows(0, 0) is false, return 0, otherwise return -1.
No celebrity exists	The algorithm should correctly identify that no person satisfies the celebrity criteria and return -1.
All people know each other	No one will satisfy the condition of not knowing anyone, so the algorithm should return -1.
One person knows everyone else	No one will satisfy the condition of being known by everyone, so the algorithm should return -1.
Large value of n (scalability)	Ensure the solution's time complexity is O(n) to handle large inputs efficiently, avoiding nested loops.
Integer overflow when calculating indices (if using bit manipulation)	Use appropriate data types and avoid operations that may lead to overflow, checking the problem constraints for maximum input sizes.
A cycle exists in the 'knows' relationship (e.g., A knows B, B knows C, C knows A)	The algorithm should still correctly identify if a celebrity exists despite the cycle, or return -1 if none exists as the celebrity must be known by everyone, and not know anyone.