Find the Celebrity

medium graph two pointers

Problem

A celebrity is known by everyone but knows nobody. Given an n-person party with a knows(a,b) oracle, return the celebrity's index, or -1 if none.

Inputn = 4, knows = {(0,1),(0,2),(1,2),(3,2)}

Output2

Person 2 is known by 0,1,3 and knows nobody.

knows edges (a→b ;)

def find_celebrity(n, knows):
    cand = 0
    for i in range(1, n):
        if knows(cand, i):
            cand = i
    for i in range(n):
        if i == cand: continue
        if knows(cand, i) or not knows(i, cand):
            return -1
    return cand

function findCelebrity(n, knows) {
  let cand = 0;
  for (let i = 1; i < n; i++) if (knows(cand, i)) cand = i;
  for (let i = 0; i < n; i++) {
    if (i === cand) continue;
    if (knows(cand, i) || !knows(i, cand)) return -1;
  }
  return cand;
}

class Solution {
    public int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; i++) if (knows(cand, i)) cand = i;
        for (int i = 0; i < n; i++) {
            if (i == cand) continue;
            if (knows(cand, i) || !knows(i, cand)) return -1;
        }
        return cand;
    }
}

int findCelebrity(int n) {
    int cand = 0;
    for (int i = 1; i < n; i++) if (knows(cand, i)) cand = i;
    for (int i = 0; i < n; i++) {
        if (i == cand) continue;
        if (knows(cand, i) || !knows(i, cand)) return -1;
    }
    return cand;
}

Explanation

A celebrity is known by everyone but knows nobody. The naive way checks every pair, but there is a slick two-pass funnel trick that uses each knows query sparingly.

In the first pass we hold one cand (candidate), starting at person 0, and walk through everyone else. If knows(cand, i) is true, then cand knows someone — so cand can't be the celebrity, and i becomes the new candidate. If false, i is not the celebrity (the real one must be known by cand), so we keep cand.

This single sweep is guaranteed to eliminate everyone except one survivor — but that survivor is only a candidate, not yet confirmed. So we run a second pass to verify: for every other person i, the candidate must not know i, and i must know the candidate. If any check fails, return -1.

Example: n = 4 with knows edges (0,1),(0,2),(1,2),(3,2). The funnel moves the candidate to 2, and verification confirms everyone knows 2 while 2 knows no one — so the answer is 2.

Each pass is one walk through the people, so the whole thing is linear in n with no extra storage.

Time: O(n) Space: O(1)