Search⌘ K

Solution: Find the Celebrity

Explore how to determine the existence of a celebrity in a gathering using stack operations and a binary matrix representation. Learn to apply an efficient O(N) solution that narrows down potential celebrities by comparing attendees and verifies the final candidate based on strict criteria. Understand both the algorithm steps and complexity analysis to prepare for coding interviews.

We'll cover the following...

Statement

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 ...