277. Find the Celebrity

Q: Why does the elimination work?

Because a celebrity knows nobody. So if cand knows i, cand is not the celebrity — i becomes the new candidate. If cand doesn't know i, i is not the celebrity (the celeb must be known by everyone, including cand). Either way, one person is ruled out per call.

Q: Why is verification needed?

Phase 1 finds the ONLY POSSIBLE celebrity. But there might be no celebrity at all — phase 2 confirms the candidate actually satisfies both properties (knows nobody, known by everyone).

mediumAsked at LinkedIn

Given n people and a knows(a, b) API, find THE celebrity — someone known by everyone but who knows no one. LinkedIn asks this because it's the canonical 'elimination by partial order' problem — n calls find a candidate, n calls verify.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

Glassdoor (2026-Q1)— LinkedIn senior IC onsite reports list Find the Celebrity among their highest-frequency mid-level questions.
Blind (2025-12)— LinkedIn writeups consistently rank this as a LinkedIn-tagged problem on public aggregators.

Problem

Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is ask questions like: 'Hi, A. Do you know B?' to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible. You are given a helper function bool knows(a, b) that tells you whether a knows b. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party. Return the celebrity's label if there is a celebrity at the party, or -1 if there is no celebrity.

Constraints

n == graph.length
n == graph[i].length
2 <= n <= 100
graph[i][j] is 0 or 1.
graph[i][i] == 1

Examples

Example 1

Input

graph = [[1,1,0],[0,1,0],[1,1,1]]

Output

Explanation: Person 1 knows nobody else and everyone knows person 1, so 1 is the celebrity.

Example 2

Input

graph = [[1,0,1],[1,1,0],[0,1,1]]

Output

-1

Explanation: There is no celebrity.

Approaches

1. Brute-force O(n^2)

For every candidate i, check that everyone else knows i and i knows no one. n^2 knows calls.

Time: O(n^2) calls
Space: O(1)

function findCelebrityBrute(n) {
  for (let i = 0; i < n; i++) {
    let ok = true;
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      if (knows(i, j) || !knows(j, i)) { ok = false; break; }
    }
    if (ok) return i;
  }
  return -1;
}

Tradeoff: Correct but the knows() calls are presumed expensive. The 'fewest calls' rubric makes this version a wrong-first-answer.

2. Two-pass: candidate elimination then verification (optimal)

Phase 1: walk i from 0 to n-1, maintaining a candidate. If candidate knows i, candidate becomes i (the candidate can't know anyone, so they're eliminated). Phase 2: verify the surviving candidate by checking they know nobody and everyone knows them.

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

function findCelebrity(n) {
  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;
}

Tradeoff: Exactly 3(n-1) knows() calls worst case. Phase 1 makes n-1 calls; Phase 2 makes 2(n-1). The elimination property: if cand knows i, cand can't be the celebrity. If cand DOESN'T know i, i can't be the celebrity (since the celeb must be known by everyone).

LinkedIn-specific tips

LinkedIn interviewers expect the elimination argument articulated EXPLICITLY: 'In phase 1, every knows(cand, i) call eliminates ONE person — either cand (if true) or i (if false). After n-1 calls I've eliminated n-1 people, so the survivor is the only possible celeb.' That sentence is the entire signal. Then verify with the second pass.

Common mistakes

Doing the elimination but skipping verification — fails when no celebrity exists.
Verifying with O(n^2) instead of O(n) — defeats the purpose of the elimination.
Swapping the direction in phase 2 (`knows(i, cand)` vs `knows(cand, i)`) — easy off-by-one in 'who knows whom'.

Follow-up questions

An interviewer at LinkedIn may pivot to one of these next:

What if there are multiple candidates? (No celebrity by definition.)
What if the knows function is asymmetric and can lie? (Becomes a fundamentally different problem.)
Implement this as an offline algorithm given the full adjacency matrix — same algorithm, no API constraint.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does the elimination work?

Because a celebrity knows nobody. So if cand knows i, cand is not the celebrity — i becomes the new candidate. If cand doesn't know i, i is not the celebrity (the celeb must be known by everyone, including cand). Either way, one person is ruled out per call.

Why is verification needed?

Phase 1 finds the ONLY POSSIBLE celebrity. But there might be no celebrity at all — phase 2 confirms the candidate actually satisfies both properties (knows nobody, known by everyone).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Find the Celebrity and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →