# Solution in C#

• The key to solving this problem is returning as soon as you know whether someone is a celebrity or not, and skipping to the next person as soon as you find someone that knows them.

Saving a bit of time is the observation that a single call to `Knows(a,b)` always excludes a person from future consideration. Why? Because if a knows b, then a is not a celeb. If a doesn't know b, then b is not a celeb (because everyone else has to know the celeb).

Since you must check, at most, every person, loop over them until you get a failure case, or exhaust the list of potential fans.

There are 2 failure cases for celebrity:

• another person (the `fan`) doesn't know the person `p`
• `p` knows a `fan`

Once either of those failure cases happens, you can skip to the next candidate. If neither happened, then you know all of the other people knew `p`, so you can immediately return `p`.

If you reach the end of the list of people without finding a celebrity, then none are, so return -1.
Given this set of people:

We see the following calls to `Knows(a,b)`:

0: `Knows(0, 1) = true` (not a celebrity)
1: `Knows(1, 0) = true` (not a celebrity)
2: `2x calls with Knows(2, [0,1]) = false, 3x calls to Knows([0,1,3], 2) = true`, no more people to check so return 2. This is our celebrity!
3: skipped

O(n) overall time complexity
O(n) space complexity.

``````public int FindCelebrity(int n)
{
if (n <= 1)
return -1;

var excluded = new bool[n]; // initialized to false!

// Loop over all the people.
for (int p = 0; p < n; p++)
{
if (excluded[p]) continue;
bool failed = false;

for (int fan = 0; fan < n; fan++)
{
if (p == fan) continue;

if (Knows(p, fan))
{
excluded[p] = true;
failed = true;
break;
}
else
{
// someone doesn't know the fan, so that fan is excluded
excluded[fan] = true;
}
if (!Knows(fan, p))
{
failed = true;
break;
}
else
{
// the fan knows someone, so fan is excluded from consideration as a celeb
excluded[fan] = true;
}
}

if (!failed)
return p;
}
return -1;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.