Solution: Find the Celebrity

Let’s solve the Find the Celebrity problem.

We'll cover the following


In a gathering of NN individuals (labeled from 00 to N1N-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×NN \times N binary matrixmatrix, where each cell contains either a 00 or a 11. If matrix[i][j]=1matrix[i][j] = 1, it signifies that person ithi^{th} knows the jthj^{th} person.

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


  • N=matrix.length=matrix[i].lengthN = matrix.length = matrix[i].length
  • 2N1002 \leq N \leq 100
  • matrix[i][j]matrix[i][j] is 00 or 11.


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, XX and YY, both purported to be celebrities. Following the celebrity criteria:

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

These conditions contradict each other, as they suggest that XX should both know and not know YY 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 11.

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 00 up to (N1N-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 11 at (i,j)(i, j) indicates that person ii knows person jj.

      • If individual xx knows individual yy, xx cannot be a celebrity; yy is considered a potential celebrity and is pushed back into the stack.
      • Otherwise, xx does not know person yy, yy is eliminated from consideration, and xx 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-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:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.