# LeetCode 277: Find the Celebrity

## Problem Restatement

There are `n` people at a party, labeled from `0` to `n - 1`.

A celebrity is a person who satisfies two conditions:

1. Everyone else knows the celebrity.
2. The celebrity knows nobody else.

We are given an API:

```python
knows(a, b)
```

It returns `True` if person `a` knows person `b`.

We need to implement:

```python
findCelebrity(n)
```

Return the celebrity label if one exists. Otherwise, return `-1`.

The LeetCode statement defines the celebrity exactly this way: all other `n - 1` people know the celebrity, while the celebrity does not know any of them.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n`, the number of people |
| API | `knows(a, b)` tells whether person `a` knows person `b` |
| Output | Celebrity label, or `-1` if no celebrity exists |
| Labels | People are labeled from `0` to `n - 1` |

Function shape:

```python
# The knows API is already defined.
# def knows(a: int, b: int) -> bool:

class Solution:
    def findCelebrity(self, n: int) -> int:
        ...
```

## Examples

Suppose `n = 3`, and person `1` is the celebrity.

The relationship looks like this:

| Person | Knows |
|---|---|
| `0` | `1` |
| `1` | nobody |
| `2` | `1` |

Then:

```python
knows(0, 1) == True
knows(2, 1) == True
knows(1, 0) == False
knows(1, 2) == False
```

So the answer is:

```python
1
```

Now suppose no celebrity exists.

For example:

```python
knows(0, 1) == True
knows(1, 0) == True
```

If two people know each other, neither can be the celebrity. A celebrity knows nobody else.

So the answer may be:

```python
-1
```

## First Thought: Brute Force

A direct solution checks every person as a possible celebrity.

For each candidate `c`, we verify two conditions against every other person `i`.

The candidate must not know `i`:

```python
knows(c, i) == False
```

And `i` must know the candidate:

```python
knows(i, c) == True
```

Code:

```python
class Solution:
    def findCelebrity(self, n: int) -> int:
        for c in range(n):
            ok = True

            for i in range(n):
                if i == c:
                    continue

                if knows(c, i) or not knows(i, c):
                    ok = False
                    break

            if ok:
                return c

        return -1
```

This is correct, but it may call `knows` many times.

For each candidate, we may compare with every other person.

The time complexity is `O(n^2)` API calls.

## Problem With Brute Force

The expensive part is checking every possible candidate.

But one call to `knows(a, b)` can eliminate one person immediately.

There are only two possibilities:

| Query | Elimination |
|---|---|
| `knows(a, b) == True` | `a` cannot be the celebrity |
| `knows(a, b) == False` | `b` cannot be the celebrity |

Why?

If `a` knows `b`, then `a` violates the celebrity rule because a celebrity knows nobody.

If `a` does not know `b`, then `b` violates the celebrity rule because everyone must know the celebrity.

So every query can remove one candidate from consideration.

## Key Insight

We can find one possible candidate in a single pass.

Start with:

```python
candidate = 0
```

Then compare the current candidate with each person `i`.

If:

```python
knows(candidate, i)
```

then `candidate` cannot be the celebrity, so `i` becomes the new candidate.

Otherwise, `i` cannot be the celebrity, so we keep the current candidate.

This process leaves at most one possible celebrity.

But it only gives a candidate. We still need a second pass to verify the two celebrity conditions.

## Algorithm

First pass: choose a candidate.

```python
candidate = 0

for i in range(1, n):
    if knows(candidate, i):
        candidate = i
```

After this loop, every person except `candidate` has been eliminated.

Second pass: verify the candidate.

For every other person `i`, check:

```python
knows(candidate, i) == False
```

and:

```python
knows(i, candidate) == True
```

If either condition fails, return `-1`.

Otherwise, return `candidate`.

## Correctness

During the first pass, we maintain the idea that every eliminated person cannot be the celebrity.

When comparing `candidate` and `i`, one of them can be eliminated.

If `candidate` knows `i`, then `candidate` cannot be the celebrity because a celebrity knows nobody. So we replace `candidate` with `i`.

If `candidate` does not know `i`, then `i` cannot be the celebrity because everyone must know the celebrity. So we keep `candidate`.

Therefore, after the first pass, only one person remains who has not been eliminated.

This person may still fail the celebrity rules. For example, they may know someone earlier in the list, or someone may not know them.

The second pass checks both required conditions against every other person. If all checks pass, the candidate is known by everyone and knows nobody else. Therefore the candidate is the celebrity.

If any check fails, no celebrity exists, because the first pass already eliminated every other person.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | One pass to find a candidate, one pass to verify |
| Space | `O(1)` | We store only one candidate variable |

The first pass uses `n - 1` calls to `knows`.

The verification pass uses up to `2(n - 1)` calls.

So the total number of API calls is at most:

```python
3 * (n - 1)
```

## Implementation

```python
# The knows API is already defined for you.
# def knows(a: int, b: int) -> bool:

class Solution:
    def findCelebrity(self, n: int) -> int:
        candidate = 0

        for i in range(1, n):
            if knows(candidate, i):
                candidate = i

        for i in range(n):
            if i == candidate:
                continue

            if knows(candidate, i):
                return -1

            if not knows(i, candidate):
                return -1

        return candidate
```

## Code Explanation

We start by assuming person `0` may be the celebrity:

```python
candidate = 0
```

Then we compare the candidate with every other person:

```python
for i in range(1, n):
```

If the current candidate knows person `i`, the current candidate cannot be the celebrity:

```python
if knows(candidate, i):
    candidate = i
```

After this pass, `candidate` is the only possible celebrity.

Then we verify the candidate.

We skip comparing the candidate with themselves:

```python
if i == candidate:
    continue
```

If the candidate knows another person, the candidate is invalid:

```python
if knows(candidate, i):
    return -1
```

If another person does not know the candidate, the candidate is invalid:

```python
if not knows(i, candidate):
    return -1
```

If no check fails, we return the candidate:

```python
return candidate
```

## Testing

LeetCode provides the `knows` API, so local tests need to simulate it with a matrix.

```python
def make_solution(graph):
    def knows(a: int, b: int) -> bool:
        return graph[a][b] == 1

    class Solution:
        def findCelebrity(self, n: int) -> int:
            candidate = 0

            for i in range(1, n):
                if knows(candidate, i):
                    candidate = i

            for i in range(n):
                if i == candidate:
                    continue

                if knows(candidate, i):
                    return -1

                if not knows(i, candidate):
                    return -1

            return candidate

    return Solution()

def test_find_celebrity():
    graph1 = [
        [0, 1, 0],
        [0, 0, 0],
        [0, 1, 0],
    ]
    assert make_solution(graph1).findCelebrity(3) == 1

    graph2 = [
        [0, 1],
        [1, 0],
    ]
    assert make_solution(graph2).findCelebrity(2) == -1

    graph3 = [
        [0],
    ]
    assert make_solution(graph3).findCelebrity(1) == 0

    graph4 = [
        [0, 1, 1],
        [0, 0, 1],
        [1, 0, 0],
    ]
    assert make_solution(graph4).findCelebrity(3) == -1

    print("all tests passed")

test_find_celebrity()
```

Test meaning:

| Test | Why |
|---|---|
| One valid celebrity | Confirms normal success case |
| Two people know each other | Confirms invalid mutual relationship |
| One person | A single person satisfies the condition |
| Candidate fails verification | Confirms the second pass is required |