For each person:
If we have no potential celebrity, let this person be the potential celebrity.
If neither of the potential celebrity nor this person knows each other, or they both know each other, reset the potential celebrity.
If the potential celebrity knows this person, but not the other way around, let this person become the new potential celebrity.
Or, simplified:
Let the first person be the potential celebrity.
For each person: (from the second)
- If the potential celebrity knows this person, let this person become the new potential celebrity.
Once done, if we have a potential celebrity, go through again and check if this person knows no-one else and everyone knows them to make sure they're actually the celebrity.
Complexity: O(n) time, O(1) space.
The keys to proving correctness are:
We can't move on from a person if that person is the celebrity, because the only criteria to move on is knowing someone else, which is not possible for the celebrity.
We'll always switch over to the celebrity if one exists, given that we go through all people and always switch over if a person knows this person, which is true for all other people with respect to the celebrity.
But, if there is no celebrity, we'll still have a (non-celebrity) candidate at the end (given that we fairly easily nominate someone as a potential celebrity), so we need to make sure the candidate is the celebrity.