Find the Celebrity

A celebrity is a special person at a party. Everyone knows them. But they know nobody. The interviewer hands you one tool to check relationships. Your job is to find the celebrity with as few checks as possible. That is the real test here.

🎯 The Problem

You are at a party with n people. The rules:

• People are numbered 0 to n - 1.
• Everyone else knows the celebrity. The celebrity is the one person everyone knows.
• The celebrity knows nobody else.
• Your only tool is knows(a, b). It returns true if person a knows person b.
• Return the celebrity. If there is no celebrity, return -1.
• The knows call is your only window into who knows whom. Make as few calls as you can.

Say there are 3 people. Person 0 knows person 1. Person 2 knows person 1. Person 1 knows nobody. So person 1 is the celebrity.

Input:  n = 3
        knows table (row a, column b = does a know b):
            0  1  2
        0 [ 0  1  0 ]
        1 [ 0  0  0 ]
        2 [ 0  1  0 ]
Output: 1

Explanation: everyone knows person 1, and person 1 knows no one.

Here is the party drawn as arrows. An arrow from a to b means a knows b. The celebrity has arrows coming in, but none going out.

🐢 Approach 1: Check Everyone Against Everyone (Brute Force)

Test each person to see if they fit the celebrity rule.

The idea:

• Pick one person at a time.
• Check if everybody else knows them.
• Check if they know nobody else.
• A person who passes both is the celebrity.

How it works:

• Loop over all n people.
• For each one, loop over everybody else and call knows.
• Return the first person who passes both checks.

Why it is weak:

• For each of the n people you scan all n people.
• That is about n times n calls to knows.
• Time is O(n²). It grows too fast as the party grows.

Here is the brute-force code for that idea:

def find_celebrity(n, knows):
    for candidate in range(n):
        good = True
        for person in range(n):
            if person == candidate:
                continue
            if knows(candidate, person) or not knows(person, candidate):
                good = False
                break
        if good:
            return candidate
    return -1

⚡ Approach 2: Candidate Elimination (Best)

One knows call removes one person from the running.

The idea:

• Keep one guess for the celebrity. Call it the candidate.
• Start with person 0 as the candidate.
• Each check throws away exactly one person.

How it works:

• Walk through everybody else, one at a time.
• Ask: does the candidate know this person?
• If yes, the candidate knows someone, so they cannot be the celebrity. Move the candidate to this person.
• If no, this person is not known by all, so they cannot be the celebrity. Keep the candidate.
• After the walk, one candidate is left.
• Verify it: confirm the candidate knows nobody and everyone knows the candidate.
• If the candidate passes, return it. If not, return -1.

Why it is fast:

• The walk takes about n checks to find the candidate.
• The verify pass adds about 2n checks.
• Total is O(n) calls, far fewer than O(n²).
• Only one candidate variable, so no extra memory.

Here is the elimination walk on our example with 3 people.

Steps to Solve

1. Start with person 0 as the candidate.
2. Walk through every other person. If the candidate knows that person, move the candidate to that person.
3. After the walk, you have one candidate left.
4. Verify the candidate. Check the candidate knows nobody and everybody knows the candidate.
5. If the candidate passes, return it. Otherwise return -1.

#include <stdio.h>

int matrix[3][3] = {
    {0, 1, 0},
    {0, 0, 0},
    {0, 1, 0}
};

int knows(int a, int b) {  // does a know b
    return matrix[a][b];
}

int findCelebrity(int n) {
    int candidate = 0;
    for (int i = 1; i < n; i++) {
        if (knows(candidate, i)) {  // candidate knows someone
            candidate = i;          // so move the candidate
        }
    }
    for (int i = 0; i < n; i++) {   // verify the candidate
        if (i == candidate) continue;
        if (knows(candidate, i) || !knows(i, candidate)) {
            return -1;  // rule broken, no celebrity
        }
    }
    return candidate;
}

int main(void) {
    printf("%d\n", findCelebrity(3));
    return 0;
}

1

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> matrix = {
    {0, 1, 0},
    {0, 0, 0},
    {0, 1, 0}
};

bool knows(int a, int b) {  // does a know b
    return matrix[a][b] == 1;
}

int findCelebrity(int n) {
    int candidate = 0;
    for (int i = 1; i < n; i++) {
        if (knows(candidate, i)) {  // candidate knows someone
            candidate = i;          // so move the candidate
        }
    }
    for (int i = 0; i < n; i++) {   // verify the candidate
        if (i == candidate) continue;
        if (knows(candidate, i) || !knows(i, candidate)) {
            return -1;  // rule broken, no celebrity
        }
    }
    return candidate;
}

int main() {
    cout << findCelebrity(3) << endl;
    return 0;
}

1

public class Celebrity {
    static int[][] matrix = {
        {0, 1, 0},
        {0, 0, 0},
        {0, 1, 0}
    };

    static boolean knows(int a, int b) {  // does a know b
        return matrix[a][b] == 1;
    }

    static int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) {  // candidate knows someone
                candidate = i;          // so move the candidate
            }
        }
        for (int i = 0; i < n; i++) {   // verify the candidate
            if (i == candidate) continue;
            if (knows(candidate, i) || !knows(i, candidate)) {
                return -1;  // rule broken, no celebrity
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        System.out.println(findCelebrity(3));
    }
}

1

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


def knows(a, b):  # does a know b
    return matrix[a][b] == 1


def find_celebrity(n):
    candidate = 0
    for i in range(1, n):
        if knows(candidate, i):   # candidate knows someone
            candidate = i         # so move the candidate
    for i in range(n):            # verify the candidate
        if i == candidate:
            continue
        if knows(candidate, i) or not knows(i, candidate):
            return -1             # rule broken, no celebrity
    return candidate


print(find_celebrity(3))

1

const matrix = [
  [0, 1, 0],
  [0, 0, 0],
  [0, 1, 0],
];

function knows(a, b) {
  // does a know b
  return matrix[a][b] === 1;
}

function findCelebrity(n) {
  let candidate = 0;
  for (let i = 1; i < n; i++) {
    if (knows(candidate, i)) {
      // candidate knows someone
      candidate = i; // so move the candidate
    }
  }
  for (let i = 0; i < n; i++) {
    // verify the candidate
    if (i === candidate) continue;
    if (knows(candidate, i) || !knows(i, candidate)) {
      return -1; // rule broken, no celebrity
    }
  }
  return candidate;
}

console.log(findCelebrity(3));

1

Let us walk through the Python version line by line. We start with candidate = 0. We just guess the first person.

The first loop runs for i in range(1, n). We compare the candidate with everyone else. The line if knows(candidate, i) asks the one question that matters. If the candidate knows person i, the candidate broke the celebrity rule. A celebrity knows nobody. So we run candidate = i to move our guess. If the candidate does not know i, then i cannot be the celebrity, because not everyone knows i. So we keep the candidate. Each step removes one person from the running.

The second loop runs for i in range(n). This is the verify step. We need it because the first loop only checked the candidate against people we passed by. The line if knows(candidate, i) or not knows(i, candidate) checks both halves of the rule at once. If the candidate knows someone, or someone does not know the candidate, the rule is broken. So we return -1. If the loop finishes with no break, the candidate is real. We return it. We skip i == candidate because nobody needs to know themselves.

⏱️ Time and Space Complexity

The brute force tests every person against every person, so it makes O(n²) calls to knows. The two-pointer version finds the candidate in one pass, then verifies it in one more pass. So it makes O(n) calls. We use no extra structure beyond a single candidate variable, so the space is O(1).

🧩 Key Takeaways

• ✅ A celebrity is known by everyone and knows nobody.
• ✅ Each knows call removes exactly one person from the running.
• ✅ One pass finds a single candidate. A second pass confirms it.
• ✅ Always verify the candidate, because the first pass alone is not proof.
• ✅ This drops the calls from O(n²) down to O(n) with O(1) extra space.

🚀 What’s Next?

• Random Pick with Weight
• Two Sum