Solution: Find the Celebrity

Statement

In a gathering of $N$ individuals (labeled from $0$ to $N-1$), there’s a possibility of one person being a celebrity. A celebrity is characterized by being known by everyone else and not knowing any attendees. This scenario is represented using an $N \times N$ binary $matrix$, where each cell contains either a $0$ or a $1$. If $matrix[i][j] = 1$, it signifies that person $i^{th}$ knows the $j^{th}$ person.

For the given $matrix$, determine the existence of a celebrity within the group. If a celebrity is identified, return its label, otherwise return $-1$.

Constraints:

• $N = matrix.length = matrix[i].length$
• $2 \leq N \leq 100$
• $matrix[i][j]$ is $0$ or $1$.

Solution

Before we delve into the solution, it’s crucial to consider the minimum and maximum number of celebrities that can exist within the given matrix.

To explore the possibility of having more than one celebrity, consider two individuals, $X$ and $Y$, both purported to be celebrities. Following the celebrity criteria:

1. $X$, being a celebrity, should not know $Y$, implying $matrix[X][Y] = 0$. Consequently, $Y$ should know $X$, or $matrix[Y][X] = 1$.
2. Conversely, for $Y$ to be a celebrity, $Y$ should not know $X$, implying $matrix[Y][X] = 0$, while $X$ must know $Y$, or $matrix[X][Y] = 1$.

These conditions contradict each other, as they suggest that $X$ should both know and not know $Y$ simultaneously, which is impossible. Thus, the assumption of having more than one celebrity contradicts the definition of a celebrity in this context. Therefore, the maximum number of celebrities possible in a matrix is $1$.

Now, let’s dive deep into the solution. To identify a celebrity at a party, this solution employs an approach utilizing a stack data structure and a binary matrix representation of individuals at the party.

Let’s walk through the steps of the solution:

1. We create a stack to hold the indexes of all attendees, treating everyone as a potential celebrity initially.

2. We populate the stack with every attendee’s index, starting from $0$ up to ($N-1$).

3. We determine potential celebrities by repeatedly popping two indexes from the stack to compare two individuals at a time.

   • For the popped individuals, we check whether one knows the other by referencing the binary matrix, where a value of $1$ at $(i, j)$ indicates that person $i$ knows person $j$.

     • If individual $x$ knows individual $y$, $x$ cannot be a celebrity; $y$ is considered a potential celebrity and is pushed back into the stack.
     • Otherwise, $x$ does not know person $y$, $y$ is eliminated from consideration, and $x$ is pushed back into the stack for further comparison.

   • Continue the process until only one index(individual) remains in the stack. This index represents the tentative celebrity.

4. Next, to verify the celebrity status, we ensure that the tentative celebrity does not know any of the other attendees (no outgoing acquaintance) while every other attendee knows them (incoming acquaintance from all).

   • We check the binary matrix for the following conditions for the tentative celebrity index:
     • The row corresponding to the tentative celebrity should have all zeros (except for the diagonal element), indicating they know no one. We do not need to check the diagonal element here.
     • The column corresponding to the tentative celebrity should have all ones (except for the diagonal element), indicating everyone knows them. We do not need to check the diagonal element here.

5. Finally, if the tentative celebrity meets the verification criteria, their index is returned as the confirmed celebrity. Otherwise, we return $-1$, signifying the absence of a celebrity.

This solution efficiently narrows down the list of potential celebrities and validates the final candidate to ensure they meet the strict criteria of being known by everyone without knowing anyone at the party.

Let’s look at the illustration below to better understand the solution: