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:

knows(a, b)

It returns True if person a knows person b.

We need to implement:

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

Function shape:

# 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:

Then:

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

So the answer is:

1

Now suppose no celebrity exists.

For example:

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:

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

knows(c, i) == False

And i must know the candidate:

knows(i, c) == True

Code:

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:

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:

candidate = 0

Then compare the current candidate with each person i.

If:

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.

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:

knows(candidate, i) == False

and:

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

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:

3 * (n - 1)

Implementation

# 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:

candidate = 0

Then we compare the candidate with every other person:

for i in range(1, n):

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

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:

if i == candidate:
    continue

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

if knows(candidate, i):
    return -1

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

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

If no check fails, we return the candidate:

return candidate

Testing

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

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: