The celebrity Problem

The problem, simply

There are n people at a party, numbered 0 to n - 1. You get a table M where M[i][j] == 1 means person i knows person j. A celebrity is a person who is known by everyone else and knows nobody.

Find the celebrity and give back their number, or -1 if there is none. There can be at most one: if two people were both celebrities, each would have to know the other, which a celebrity never does.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check every person directly.

1. For each person c: check that M[c][j] == 0 for every other j (knows nobody).
2. Check that M[j][c] == 1 for every other j (known by everyone).
3. If both hold, return c. If nobody passes, return -1.

class Solution {
    public int celebrity(int[][] M) {
        int n = M.length;
        for (int c = 0; c < n; c++) {
            boolean ok = true;
            for (int j = 0; j < n && ok; j++) {
                if (j == c) continue;
                if (M[c][j] == 1 || M[j][c] == 0) ok = false;  // knows someone, or someone does not know c
            }
            if (ok) return c;
        }
        return -1;
    }
}

How long it takes: up to n people times n checks, O(n^2). Extra room: O(1).

Way 2: the clever way

Use the knock out rule with a stack.

1. Push every person onto a stack.
2. While more than one person is on the stack: pop a and b. If a knows b, a is out, so push b back. Otherwise b is out, so push a back.
3. One candidate c is left. Check it: c must know nobody, and everyone else must know c. If either check fails, return -1.

import java.util.*;

class Solution {
    public int celebrity(int[][] M) {
        int n = M.length;
        if (n == 0) return -1;                           // nobody at the party
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) stack.push(i);       // everyone might be the one
        while (stack.size() > 1) {
            int a = stack.pop(), b = stack.pop();
            if (M[a][b] == 1) stack.push(b);             // a knows b: a is out
            else stack.push(a);                          // a does not know b: b is out
        }
        int c = stack.pop();
        for (int j = 0; j < n; j++) {                    // the last one must pass the full check
            if (j == c) continue;
            if (M[c][j] == 1 || M[j][c] == 0) return -1;
        }
        return c;
    }
}

How long it takes: n - 1 questions to knock people out, then at most 2(n - 1) questions to check, O(n). Extra room: the stack of n people, O(n).

Another way: two pointers, no stack

You do not need the stack. Put one finger on person 0 and one on person n - 1. Ask if the left one knows the right one. If yes, the left one is out, so move the left finger right. If no, the right one is out, so move the right finger left. When the fingers meet, that person is the candidate.

class Solution {
    public int celebrity(int[][] M) {
        int n = M.length;
        if (n == 0) return -1;
        int lo = 0, hi = n - 1;
        while (lo < hi) {
            if (M[lo][hi] == 1) lo++;      // lo knows hi: lo is out
            else hi--;                     // lo does not know hi: hi is out
        }
        int c = lo;
        for (int j = 0; j < n; j++) {
            if (j == c) continue;
            if (M[c][j] == 1 || M[j][c] == 0) return -1;
        }
        return c;
    }
}

Same O(n) time, and only O(1) extra room. This is the answer most interviewers hope to hear last.

Watch out for

• Counting M[c][c]. The diagonal says whether a person "knows themselves", and it must be ignored in both checks.
• Asking M[b][a] when you meant M[a][b]. Write the rule down: "a knows b means a is out".
• Thinking there might be two celebrities. There is at most one, so return as soon as the single candidate passes.

What interviewers ask next

• The table is hidden and you only have a function knows(a, b), which is expensive. How many calls do you need? At most 3(n - 1): n - 1 to eliminate and 2(n - 1) to check. You can save a few by remembering answers you already got during elimination.
• Can you prove O(n) questions are needed? Yes. If any person were never asked about, you could not tell whether they are the celebrity, so every person must be involved in some question.
• Graph view: the celebrity is a node with n - 1 arrows coming in and 0 going out. With the table you can find it by in-degree and out-degree, but that reads all n^2 cells.
• Find the town judge (LeetCode 997): the same idea with a list of "trusts" pairs. Count in-degree minus out-degree and look for n - 1.

Remember this

Grown-up words: the party is a directed graph, the knows table is an adjacency matrix, the celebrity is a universal sink (in-degree n - 1, out-degree 0), the knock out game is elimination, and the two fingers are the two pointer technique.