The Celebrity Problem: Efficient Algorithm Solution

Sasank Nasika
Written by
Sasank Nasika
Sasank Nasika
Sasank Nasika

Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.

All articles by
Sasank Nasika
Edited by
Kaustubh Saini
Kaustubh Saini
Kaustubh Saini

Kaustubh Saini writes about software development in a way that’s easy to follow and genuinely helpful. He breaks down complex topics-from AI to the latest in tech-so they actually make sense. His goal is simple: help others learn, stay curious, and keep up with a fast-changing world.

All articles by
Kaustubh Saini
Last updated on
May 14, 2025
In this blog, we'll tackle the "Celebrity Problem" and walk through an efficient algorithm to identify the celebrity in a party, minimizing time complexity.
The Celebrity Problem: Efficient Algorithm Solution

Problem Statement

In a party of n people, a "celebrity" is defined as someone who:

  1. Doesn't know anyone at the party
  2. Everyone else at the party knows the celebrity

Your task is to find the celebrity in the party (if one exists). You are given a helper function knows(A, B) which returns true if person A knows person B, and false otherwise.

The problem can be represented using an n×n matrix where:

  • matrix[i][j] = 1 if person i knows person j
  • matrix[i][j] = 0 if person i doesn't know person j

Note that a person cannot know themselves, so matrix[i][i] = 0 for all i.

Brute Force Approach

Explanation

The simplest way to solve this problem is to check each person and verify if they meet both celebrity conditions:

  1. They don't know anyone (all zeros in their row)
  2. Everyone knows them (all ones in their column, except the diagonal element)

For each person, we'll need to scan an entire row and column of the matrix, making this approach straightforward but not very efficient.

The brute force approach has:

  • Time Complexity: O(n²) since for each of the n people, we check n-1 relationships
  • Space Complexity: O(1) as we only use a constant amount of extra space

Here P2 is a celebrity .

Python Code

def findCelebrity(n, knows):
    # Helper function to check if person i is a celebrity
    def isCelebrity(i):
        # Check if i knows anyone
        for j in range(n):
            if i != j and knows(i, j):
                return False  # i knows someone, so not a celebrity

        # Check if everyone knows i
        for j in range(n):
            if i != j and not knows(j, i):
                return False  # Someone doesn't know i, so not a celebrity

        return True  # i meets both celebrity conditions

    # Check each person
    for i in range(n):
        if isCelebrity(i):
            return i  # Found the celebrity

    return -1  # No celebrity exists

C++ Code

int findCelebrity(int n, function<bool(int, int)> knows) {
    // Helper function to check if person i is a celebrity
    auto isCelebrity = [&](int i) {
        // Check if i knows anyone
        for (int j = 0; j < n; j++) {
            if (i != j && knows(i, j)) {
                return false;  // i knows someone, so not a celebrity
            }
        }

        // Check if everyone knows i
        for (int j = 0; j < n; j++) {
            if (i != j && !knows(j, i)) {
                return false;  // Someone doesn't know i, so not a celebrity
            }
        }

        return true;  // i meets both celebrity conditions
    };

    // Check each person
    for (int i = 0; i < n; i++) {
        if (isCelebrity(i)) {
            return i;  // Found the celebrity
        }
    }

    return -1;  // No celebrity exists
}

Java Code

// The knows API is defined in the parent class
// boolean knows(int a, int b);

public int findCelebrity(int n) {
    // Helper function to check if person i is a celebrity
    Predicate<Integer> isCelebrity = i -> {
        // Check if i knows anyone
        for (int j = 0; j < n; j++) {
            if (i != j && knows(i, j)) {
                return false;  // i knows someone, so not a celebrity
            }
        }

        // Check if everyone knows i
        for (int j = 0; j < n; j++) {
            if (i != j && !knows(j, i)) {
                return false;  // Someone doesn't know i, so not a celebrity
            }
        }

        return true;  // i meets both celebrity conditions
    };

    // Check each person
    for (int i = 0; i < n; i++) {
        if (isCelebrity.test(i)) {
            return i;  // Found the celebrity
        }
    }

    return -1;  // No celebrity exists
}

Optimized Approach

Explanation

We can optimize this solution by using the fact that if A knows B, then A cannot be the celebrity. Similarly, if A doesn't know B, then B cannot be the celebrity.

The optimized strategy works in two phases:

  1. Elimination phase: Find a potential celebrity candidate
  • Start with person 0 as the candidate
  • For each other person i:
  • If the candidate knows i, then the candidate cannot be a celebrity, so i becomes the new candidate
  • If the candidate doesn't know i, then i cannot be a celebrity, so the candidate remains the same
  1. Verification phase: Verify if the candidate is actually a celebrity
  • Check if the candidate knows no one
  • Check if everyone knows the candidate

This approach reduces the number of calls to the knows function significantly.

The optimized approach has:

  • Time Complexity: O(n) as we make at most 3n calls to the knows function
  • Space Complexity: O(1) as we only use a constant amount of extra space

Let's Consider The Following example,

We start with 4 candidates (0-3) and need to find the best match based on compatibility with 4 people (0-3). Y means compatible, N means not compatible.

We Assume Celebrity be Zero,

Then Zero Knows One,So candidate = 1,

One knows two, So candidate = 2,

Two knows Three ,so Candidate = 3.

Lets Verify if 3 is a Celebrity.

We Can see Three knows 0,1,2 so 3 can’t be celebrity so there is no celebrity in this case.

Celebrity Problem Visualization

<visualization-box>

Python Code

def findCelebrity(n, knows):
    # Phase 1: Find a potential celebrity candidate
    candidate = 0
    for i in range(1, n):
        if knows(candidate, i):
            # If candidate knows i, candidate cannot be a celebrity
            # i becomes the new candidate
            candidate = i

    # Phase 2: Verify the candidate
    # Check if candidate knows no one
    for i in range(n):
        if i != candidate and knows(candidate, i):
            return -1  # Candidate knows someone, so not a celebrity

    # Check if everyone knows the candidate
    for i in range(n):
        if i != candidate and not knows(i, candidate):
            return -1  # Someone doesn't know the candidate, so not a celebrity

    return candidate  # Found the celebrity

C++ Code

#include <functional>

int findCelebrity(int n, std::function<bool(int, int)> knows) {
    // Phase 1: Find a potential celebrity candidate
    int candidate = 0;
    for (int i = 1; i < n; i++) {
        if (knows(candidate, i)) {
            // If candidate knows i, candidate cannot be a celebrity
            // i becomes the new candidate
            candidate = i;
        }
    }

    // Phase 2: Verify the candidate
    // Check if candidate knows no one
    for (int i = 0; i < n; i++) {
        if (i != candidate && knows(candidate, i)) {
            return -1;  // Candidate knows someone, so not a celebrity
        }
    }

    // Check if everyone knows the candidate
    for (int i = 0; i < n; i++) {
        if (i != candidate && !knows(i, candidate)) {
            return -1;  // Someone doesn't know the candidate, so not a celebrity
        }
    }

    return candidate;  // Found the celebrity
}

Java Code

// The knows API is defined in the parent class
// boolean knows(int a, int b);

public int findCelebrity(int n) {
    // Phase 1: Find a potential celebrity candidate
    int candidate = 0;
    for (int i = 1; i < n; i++) {
        if (knows(candidate, i)) {
            // If candidate knows i, candidate cannot be a celebrity
            // i becomes the new candidate
            candidate = i;
        }
    }

    // Phase 2: Verify the candidate
    // Check if candidate knows no one
    for (int i = 0; i < n; i++) {
        if (i != candidate && knows(candidate, i)) {
            return -1;  // Candidate knows someone, so not a celebrity
        }
    }

    // Check if everyone knows the candidate
    for (int i = 0; i < n; i++) {
        if (i != candidate && !knows(i, candidate)) {
            return -1;  // Someone doesn't know the candidate, so not a celebrity
        }
    }

    return candidate;  // Found the celebrity
}

Conclusion

The Celebrity Problem teaches important lessons about using problem constraints to optimize solutions. By recognizing that a celebrity must follow specific relationship patterns, we reduced the time complexity from O(n²) to O(n).
The key insight was that we could eliminate candidates efficiently: if A knows B, A cannot be the celebrity; if A doesn't know B, B cannot be the celebrity. This logical deduction allowed us to find a potential candidate with just n-1 comparisons.

FAQs

TAGS

Arrays
Your resume just got a serious upgrade.
AI-optimized. Recruiter-approved.
Build your winning resume
They’re judging your every word.
Our AI shows you how to sound confident and hireable — instantly.
Rehearse with a pro (AI)
FAQ Question
Arrow

FAQ Answer

Revolutionizing Interview Preparation with AI

Try it now - It’s free!