The Celebrity Problem

Q: What is the time complexity of the celebrity problem?

The elimination solutions run in O(n) time: n-1 lookups find the candidate and at most 2(n-1) check it. The two-pointer version uses O(1) extra space and the stack version O(n) . Checking every person against the definition costs O(n²) .

Q: Can there be more than one celebrity?

No. If two people were both celebrities, each would be known by everyone, so each would know the other. But a celebrity knows no one, so a party has at most one celebrity.

Q: How is the celebrity problem related to graphs?

The matrix is the adjacency matrix of a directed graph: an edge from i to j means i knows j . A celebrity is a node with out-degree 0 and in-degree n-1 , a universal sink. Counting degrees reads the whole matrix, while elimination finds the sink after reading only O(n) cells.

MediumStack Two pointers Graphs

+10

There are n people at a party, numbered from 0 to n-1. You get an n × n matrix where matrix[i][j] is 1 if person i knows person j and 0 if not. Knowing is one-way: i can know j while j does not know i.

A celebrity is a person whom every other person knows and who knows no one. Return the celebrity's number, or -1 if there is no celebrity.

Function

findCelebrity(matrix: integer-2d-array) → integer

matrixinteger-2d-array: who knows whom: row i, column j is 1 if person i knows person j
Returnsinteger: the celebrity's number, or -1 if there is none

Constraints

2 ≤ n ≤ 150, where n is the number of rows and of columns
matrix[i][j] is 0 or 1
matrix[i][i] = 0 for every person

Examples

Input: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Output: 1
Explanation: Row 1 is all zeros, so person 1 knows no one. Column 1 has a 1 in rows 0 and 2, so both other people know person 1. Person 1 is the celebrity.

Follow-up

Suppose each lookup is a question you must ask. How few questions do you need in the worst case, and can you get below 3(n-1)?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Testing every person against the definition takes about 2n² lookups. One cell matrix[a][b] always rules out one of a and b, so n-1 lookups leave a single candidate. One pass over the candidate's row and column then decides whether it is the celebrity.

Check every person

Intuition

Person c is the celebrity when row c holds no 1 (they know no one) and column c holds a 1 in every row but their own (everyone knows them). Test that definition for each person in turn and return the first one who passes.

Each person costs up to 2(n-1) lookups, about 2n² in total: n = 150 means about 45,000 lookups.

Algorithm

For each person c from 0 to n-1, look at every other person other.
If matrix[c][other] is 1, or matrix[other][c] is 0, c is not the celebrity: move to the next person.
If no other person rules c out, return c.
If every person fails, return -1.

def findCelebrity(matrix):
    n = len(matrix)
    for c in range(n):
        is_celebrity = True
        for other in range(n):
            # c must know no one, and everyone else must know c.
            if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
                is_celebrity = False
                break
        if is_celebrity:
            return c
    return -1

Eliminate with a stack

Intuition

If matrix[a][b] is 1, a knows someone and cannot be the celebrity. If it is 0, a does not know b, so b cannot be the celebrity. Either way one lookup removes one person for good. Put everyone on a stack, pop two, ask, and push back the one still possible: after n-1 rounds one person is left.

That person is a candidate, not an answer. Elimination shows that nobody else can be the celebrity, but never checks the survivor's row and column. In the third example the survivor is person 2, who knows person 3, so the check returns -1. The check costs 2(n-1) more lookups, O(n) in total.

Algorithm

Push every person onto a stack.
While the stack holds more than one person, pop a and b.
If a knows b, push b back; otherwise push a back.
Take the last person as the candidate. If they know anyone, or anyone does not know them, return -1.
Otherwise return the candidate.

def findCelebrity(matrix):
    n = len(matrix)
    candidates = list(range(n))
    # Each question removes one person who cannot be the celebrity.
    while len(candidates) > 1:
        a = candidates.pop()
        b = candidates.pop()
        candidates.append(b if matrix[a][b] == 1 else a)
    c = candidates[0]
    # The survivor is only a candidate: check every other person.
    for other in range(n):
        if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
            return -1
    return c

Two pointers, then verify

Intuition

The stack only holds people not yet ruled out, and their order does not matter. Replace it with two pointers, a at the first person and b at the last: everyone outside the range from a to b is already out. If a knows b, a is out; otherwise b is out. When the pointers meet, the person under them is the candidate.

In the first example, matrix[0][2] is 0, so person 2 is out; then matrix[0][1] is 1, so person 0 is out. The pointers meet at person 1, who passes the check. That is n-1 lookups plus at most 2(n-1), with two integers of extra memory.

Algorithm

Set a = 0 and b = n-1.
While a < b: if matrix[a][b] is 1, add 1 to a; otherwise subtract 1 from b.
The candidate is a. For every other person, check that the candidate does not know them and that they know the candidate.
Return the candidate if every check holds, otherwise -1.

def findCelebrity(matrix):
    n = len(matrix)
    a, b = 0, n - 1
    # Each question rules out one of the two people.
    while a < b:
        if matrix[a][b] == 1:
            a += 1  # a knows someone, so a is not the celebrity
        else:
            b -= 1  # a does not know b, so b is not the celebrity
    # a is the only person left who could be the celebrity: check it.
    for other in range(n):
        if other != a and (matrix[a][other] == 1 or matrix[other][a] == 0):
            return -1
    return a

Pitfalls and edge cases

Returning the survivor without checking it. In [[0, 1], [1, 0]] the survivor is one of two people who know each other, and the answer is -1.
Checking only one side. The third example fails only on the row: everyone knows person 2, but person 2 knows person 3.
Counting the diagonal. matrix[c][c] is 0, so a column check that does not skip other == c rejects every real celebrity.
Reading the cell backward. matrix[a][b] = 1 rules out a, not b. Swapping the roles throws away the real celebrity.
Returning a 1-based index in Lua or R. People are numbered from 0, so subtract 1 before you return.

Frequently asked questions3

What is the time complexity of the celebrity problem?

The elimination solutions run in O(n) time: n-1 lookups find the candidate and at most 2(n-1) check it. The two-pointer version uses O(1) extra space and the stack version O(n). Checking every person against the definition costs O(n²).

Can there be more than one celebrity?

No. If two people were both celebrities, each would be known by everyone, so each would know the other. But a celebrity knows no one, so a party has at most one celebrity.

How is the celebrity problem related to graphs?

The matrix is the adjacency matrix of a directed graph: an edge from i to j means i knows j. A celebrity is a node with out-degree 0 and in-degree n-1, a universal sink. Counting degrees reads the whole matrix, while elimination finds the sink after reading only O(n) cells.

def findCelebrity(matrix):
    # Write code here

Test #1

Test #2

Test #3

Argument

matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]

Expected Output

The Celebrity Problem

Function

Constraints

Examples

Hints

Solution

Check every person

Eliminate with a stack

Two pointers, then verify

Pitfalls and edge cases

Frequently asked questions3

Similar problems