The Celebrity Problem — Medium Problem & Solution

Problem statement

At a party of n people, numbered 0 to n - 1, the square matrix mat records who knows whom: mat[i][j] = 1 means person i knows person j, and 0 means they do not. The diagonal mat[i][i] says nothing about anyone and must be ignored (it may hold 0 or 1).

A celebrity is a person who is known by everyone else but knows nobody else. There is at most one celebrity. Return the celebrity's index, or -1 if there is none.

Example 1

Input: mat = [[0,1,0],[0,0,0],[0,1,0]]
Output: 1
Explanation: Persons 0 and 2 both know person 1, and person 1 knows nobody.

Example 2

Input: mat = [[0,1],[1,0]]
Output: -1
Explanation: Each knows the other, so neither is a celebrity.

Example 3

Input: mat = [[1]]
Output: 0
Explanation: Alone at the party, person 0 qualifies — the diagonal is ignored.

Constraints

• 1 <= n <= 3000
• mat.length == mat[i].length == n
• mat[i][j] is 0 or 1

How to solve The Celebrity Problem

Every 'does a know b?' query eliminates one of the two, so n - 1 queries leave a single candidate; one O(n) check then confirms or rejects it.

Approach

1. Set a = 0, b = n - 1.
2. While a < b: if mat[a][b] == 1, a knows someone and cannot be the celebrity, so a++; otherwise b is not known by a and cannot be the celebrity, so b--.
3. The candidate is c = a. For every i != c, require mat[c][i] == 0 and mat[i][c] == 1.
4. Return c if all checks pass, otherwise -1.

Why it works

Each comparison removes a person who provably is not the celebrity, and the range [a, b] always still contains the celebrity if one exists. So after the loop the only possible celebrity is c; the final scan checks the definition directly, which also handles the case where nobody qualifies.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The elimination only produces a candidate — skipping the verification returns a wrong index when there is no celebrity.
• Ignore the diagonal in the verification: mat[c][c] may be 1.
• Check both conditions: knows nobody (row is all 0) and is known by everyone (column is all 1).

Reference solution

Python

from typing import List

def celebrity(mat: List[List[int]]) -> int:
    n = len(mat)
    a, b = 0, n - 1
    while a < b:
        if mat[a][b] == 1:
            a += 1
        else:
            b -= 1
    c = a
    for i in range(n):
        if i != c and (mat[c][i] == 1 or mat[i][c] == 0):
            return -1
    return c

JavaScript

var celebrity = function(mat) {
    var n = mat.length;
    var a = 0, b = n - 1;
    while (a < b) {
        if (mat[a][b] === 1) a++;
        else b--;
    }
    for (var i = 0; i < n; i++) {
        if (i !== a && (mat[a][i] === 1 || mat[i][a] === 0)) return -1;
    }
    return a;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium