Universal Sink (Celebrity Problem)

The Celebrity Problem (also called the Universal Sink) is a classic graph puzzle that looks like it needs O(n²) work but collapses to O(n) once you notice a sharp trick: a single "knows" relationship can eliminate a candidate forever.

The slow way first

The brute-force check: for every person c, scan their whole row and whole column to see if they know nobody and are known by everybody. That is n work per person across n people — O(n²) matrix lookups.

The question to ask: can one comparison rule out more than one person at a time? It turns out a single lookup knows(a, b) always eliminates exactly one of the two people from being the celebrity.

The idea: eliminate, then confirm

Pick any two people a and b and ask knows(a, b):

• If a knows b, then a cannot be the celebrity (a celebrity knows nobody). Eliminate a.
• If a does NOT know b, then b cannot be the celebrity (everyone must know the celebrity, but a does not know b). Eliminate b.

Either way one person is gone. Sweep a single candidate pointer across all n people and after n − 1 comparisons exactly one survivor remains. That survivor is the only possible celebrity — but elimination does not prove they qualify, so we verify: their row must be all zeros and their column all ones.

Walk through it

Step through the animation. The candidate pointer starts at person 0. Each comparison reads one matrix cell: if the candidate knows someone, the candidate is dropped and that someone becomes the new candidate; if not, the other person is dropped. Person 2 survives the sweep. We then light up row 2 (all zeros — knows nobody) and column 2 (all ones — known by all), confirming the celebrity.

Pseudocode

cand = 0
for i from 1 to n-1:                 # elimination sweep
    if knows(cand, i):
        cand = i                     # cand knows someone -> cand is out
    # else i is out, cand stays
for j in all people:                 # verify: cand knows nobody
    if j != cand and knows(cand, j):
        return -1
for i in all people:                 # verify: everyone knows cand
    if i != cand and not knows(i, cand):
        return -1
return cand

The Python solution

def find_celebrity(knows, n):
    # knows(a, b) is True if a knows b  (M[a][b] == 1)
    cand = 0
    for i in range(1, n):
        if knows(cand, i):
            cand = i          # cand knows i -> cand is out
        # else: i is out, cand stays
    for j in range(n):        # cand must know nobody
        if j != cand and knows(cand, j):
            return -1
    for i in range(n):        # everyone must know cand
        if i != cand and not knows(i, cand):
            return -1
    return cand

• cand is the running candidate; it starts at person 0.
• The first loop is the elimination sweep: each knows(cand, i) lookup drops exactly one person. If the candidate knows i, the candidate is disqualified and i takes over; otherwise i is disqualified and the candidate stays.
• After the sweep, cand is the only possible celebrity — but not yet proven.
• The second loop confirms the candidate knows nobody (an all-zero row).
• The third loop confirms everyone knows the candidate (an all-one column). Both must hold, or there is no celebrity and we return -1.

Complexity

The elimination sweep does n − 1 comparisons and verification does at most 2n more — all O(n) lookups, with only a single integer of extra state. No hash map, no recursion: the win comes purely from the observation that one comparison eliminates one candidate.

When this pattern shows up

Practice