Topics › Stacks and Queues › Implementation Problems

Celebrity Problem

Hard TUF ID 957 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

There are n people at a party, numbered 0 to n - 1. You are given an n × n matrix M where M[i][j] == 1 means person i knows person j. A celebrity is a person who is known by everyone else but knows nobody else. Return the celebrity’s index, or -1 if there is none.

The diagonal M[i][i] says whether someone knows themselves, which is irrelevant; some versions fill it with 0, others with 1. All three methods below ignore it. The LeetCode version (Find the Celebrity) hides the matrix behind a knows(a, b) function and asks you to minimise calls; the same algorithms apply, with M[a][b] replaced by knows(a, b).

Constraints: n is up to a few thousand, so the matrix has millions of cells; M[i][j] is 0 or 1.

Example 1

M = [[0, 1, 0],
     [0, 0, 0],
     [0, 1, 0]]
answer = 1     // 0 and 2 both know 1, and 1 knows nobody

Example 2

M = [[0, 1],
     [1, 0]]
answer = -1    // 0 and 1 know each other, so neither "knows nobody"

There is at most one celebrity. If a and b were both celebrities, then a would know b (everyone knows a celebrity) and a would know nobody (a celebrity knows no one). Contradiction. So the answer is a single index or -1.

Approach 1: Brute force, count in-degrees and out-degrees

Intuition. Think of the matrix as a directed graph with an edge i → j when i knows j. A celebrity has in-degree n - 1 (everyone points at them) and out-degree 0 (they point at nobody). Read the whole matrix once and count both degrees for every person.

Algorithm.

1. For every pair i ≠ j with M[i][j] == 1: increment iKnow[i] and knowMe[j].
2. Return the first i with knowMe[i] == n - 1 and iKnow[i] == 0, or -1.

static int bruteForce(int[][] m) {
    int n = m.length;
    int[] knowMe = new int[n], iKnow = new int[n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && m[i][j] == 1) { iKnow[i]++; knowMe[j]++; }
    for (int i = 0; i < n; i++)
        if (knowMe[i] == n - 1 && iKnow[i] == 0) return i;
    return -1;
}

Complexity. Time O(n^2): every cell is read. Space O(n) for the two counters.

Reading the whole matrix seems unavoidable at first, but it is not. Most cells never need to be looked at.

Approach 2: Better, eliminate with a stack

Intuition. A single question about two people always rules one of them out:

• If a knows b, then a is not the celebrity, because a celebrity knows nobody.
• If a does not know b, then b is not the celebrity, because everyone knows the celebrity.

So put everyone on a stack. Repeatedly pop two people, ask one question, and push back only the one who might still be the celebrity. Each question removes one person, so after n - 1 questions exactly one candidate remains.

Elimination only proves that nobody else can be the celebrity. It does not prove that the candidate is one; maybe there is no celebrity at all. So finish by checking the candidate’s whole row (they must know nobody) and column (everyone must know them), which costs 2(n - 1) more lookups.

Algorithm.

1. Push 0 .. n-1.
2. While more than one person is on the stack: pop a and b; push b if M[a][b] == 1, else push a.
3. Verify the last person c: for every j ≠ c, require M[c][j] == 0 and M[j][c] == 1.

static int better(int[][] m) {
    int n = m.length;
    if (n == 0) return -1;
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) st.push(i);
    while (st.size() > 1) {
        int a = st.pop(), b = st.pop();
        if (m[a][b] == 1) st.push(b);             // a knows b, so a is not the celebrity
        else st.push(a);                          // a does not know b, so b is not the celebrity
    }
    int c = st.pop();
    return isCelebrity(m, c) ? c : -1;
}

static boolean isCelebrity(int[][] m, int c) {
    for (int j = 0; j < m.length; j++) {
        if (j == c) continue;
        if (m[c][j] == 1 || m[j][c] == 0) return false;
    }
    return true;
}

Complexity. Time O(n): n - 1 elimination questions plus 2(n - 1) verification lookups. Space O(n) for the stack.

Approach 3: Optimal, two pointers

Intuition. The stack is only a container for “people not yet eliminated”. Any order of elimination works, so we can do without it. Keep one pointer top at the start and one pointer bottom at the end. Everyone outside top..bottom has been eliminated. Ask whether top knows bottom:

• yes: top knows someone, so top is not the celebrity; move top forward.
• no: bottom is unknown to top, so bottom is not the celebrity; move bottom back.

When the pointers meet, the remaining person is the only candidate. Verify exactly as before.

Algorithm.

1. top = 0, bottom = n - 1.
2. While top < bottom: if M[top][bottom] == 1, top++; else bottom--.
3. Return top if it passes the row and column check, else -1.

static int optimal(int[][] m) {
    int n = m.length;
    if (n == 0) return -1;
    int top = 0, bottom = n - 1;
    while (top < bottom) {
        if (m[top][bottom] == 1) top++;           // top knows someone: not the celebrity
        else bottom--;                            // nobody unknown to top can be the celebrity
    }
    return isCelebrity(m, top) ? top : -1;
}

Dry run on

M = [[0, 1, 1, 0],
     [0, 0, 0, 0],
     [0, 1, 0, 0],
     [1, 1, 0, 0]]

The candidate is 1. Row 1 is all zeros and column 1 is 1 for people 0, 2 and 3, so the answer is 1.

Complexity. Time O(n) with at most 3(n - 1) matrix lookups in total. Space O(1).

Edge cases and pitfalls

• Always verify the candidate. In [[0,1,0],[0,0,0],[0,0,0]] elimination ends on a person who is not a celebrity (person 1 knows nobody, but person 2 does not know them). Skipping the check returns a wrong index.
• Diagonal values. If M[i][i] == 1, a naive “row of the celebrity is all zeros” check fails. Skip j == c in the check, and skip i == j when counting degrees. The elimination steps never compare a person with themselves.
• Mutual acquaintance. [[0,1],[1,0]] returns -1: both know someone.
• Nobody knows anybody. With n ≥ 2 and an all-zero matrix, everyone knows nobody, but nobody is known; the answer is -1.
• A single person. With n == 1, the conditions “everyone else knows them” and “they know nobody else” hold vacuously, so the answer is 0. The brute force gets this right because n - 1 == 0.
• Empty party. n == 0 returns -1; the stack and two-pointer versions guard it explicitly.

Related problems

• Asteroid Collision also resolves pairwise “fights” on a stack, where each fight removes at least one contestant.
• Implement Stack using Arrays builds the container that Approach 2 relies on.
• Two Sum has a two-pointer solution where every comparison discards one end, just like Approach 3.
• Stock span problem is another problem from the same section where a stack removes candidates that can no longer win.