Celebrity Problem

Find the celebrity in a party of n people using the minimum number of questions.

Language Selection

Choose your preferred programming language

Showing: Python

Celebrity Problem

Problem Statement

In a party of n people, there is one celebrity. A celebrity is someone who:

  1. Knows nobody else
  2. Is known by everyone else

You are given a helper function knows(a, b) which returns true if person a knows person b, false otherwise.

Find the celebrity using the minimum number of questions (calls to knows function).

Examples

Example 1:

Input: n = 2
knows(0, 1) = true
knows(1, 0) = false

Output: 1
Explanation: Person 1 is the celebrity because:
- Person 1 knows nobody (knows(1, 0) = false)
- Person 0 knows person 1 (knows(0, 1) = true)

Constraints

  • 1 <= n <= 100
  • knows(a, b) returns true if person a knows person b, false otherwise
  • There is exactly one celebrity or no celebrity

Approach 1: Two Pointers (Optimal)

Algorithm

Use two pointers to eliminate candidates efficiently. If A knows B, then A cannot be celebrity. If A doesn’t know B, then B cannot be celebrity.

Steps:

  1. Start with two pointers at first and last person
  2. If left knows right, left cannot be celebrity (move left++)
  3. If left doesn’t know right, right cannot be celebrity (move right–)
  4. Continue until only one candidate remains
  5. Verify the remaining candidate is actually a celebrity

Implementation

Python:

def findCelebrity(n):
    """
    Find celebrity using two pointers approach
    Time: O(n)
    Space: O(1)
    """
    left, right = 0, n - 1
    
    # Eliminate candidates using two pointers
    while left < right:
        if knows(left, right):
            left += 1  # left knows right, so left cannot be celebrity
        else:
            right -= 1  # left doesn't know right, so right cannot be celebrity
    
    # left == right, this is our candidate
    candidate = left
    
    # Verify the candidate is actually a celebrity
    for i in range(n):
        if i != candidate:
            # Celebrity should not know anyone
            if knows(candidate, i):
                return -1
            # Everyone should know the celebrity
            if not knows(i, candidate):
                return -1
    
    return candidate

Java:

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int left = 0, right = n - 1;
        
        // Eliminate candidates using two pointers
        while (left < right) {
            if (knows(left, right)) {
                left++;  // left knows right, so left cannot be celebrity
            } else {
                right--;  // left doesn't know right, so right cannot be celebrity
            }
        }
        
        // left == right, this is our candidate
        int candidate = left;
        
        // Verify the candidate is actually a celebrity
        for (int i = 0; i < n; i++) {
            if (i != candidate) {
                // Celebrity should not know anyone
                if (knows(candidate, i)) {
                    return -1;
                }
                // Everyone should know the celebrity
                if (!knows(i, candidate)) {
                    return -1;
                }
            }
        }
        
        return candidate;
    }
}

Go:

func findCelebrity(n int) int {
    left, right := 0, n-1
    
    // Eliminate candidates using two pointers
    for left < right {
        if knows(left, right) {
            left++  // left knows right, so left cannot be celebrity
        } else {
            right--  // left doesn't know right, so right cannot be celebrity
        }
    }
    
    // left == right, this is our candidate
    candidate := left
    
    // Verify the candidate is actually a celebrity
    for i := 0; i < n; i++ {
        if i != candidate {
            // Celebrity should not know anyone
            if knows(candidate, i) {
                return -1
            }
            // Everyone should know the celebrity
            if !knows(i, candidate) {
                return -1
            }
        }
    }
    
    return candidate
}

JavaScript:

function findCelebrity(n) {
    let left = 0, right = n - 1;
    
    // Eliminate candidates using two pointers
    while (left < right) {
        if (knows(left, right)) {
            left++;  // left knows right, so left cannot be celebrity
        } else {
            right--;  // left doesn't know right, so right cannot be celebrity
        }
    }
    
    // left == right, this is our candidate
    const candidate = left;
    
    // Verify the candidate is actually a celebrity
    for (let i = 0; i < n; i++) {
        if (i !== candidate) {
            // Celebrity should not know anyone
            if (knows(candidate, i)) {
                return -1;
            }
            // Everyone should know the celebrity
            if (!knows(i, candidate)) {
                return -1;
            }
        }
    }
    
    return candidate;
}

C#:

public class Solution : Relation {
    public int FindCelebrity(int n) {
        int left = 0, right = n - 1;
        
        // Eliminate candidates using two pointers
        while (left < right) {
            if (Knows(left, right)) {
                left++;  // left knows right, so left cannot be celebrity
            } else {
                right--;  // left doesn't know right, so right cannot be celebrity
            }
        }
        
        // left == right, this is our candidate
        int candidate = left;
        
        // Verify the candidate is actually a celebrity
        for (int i = 0; i < n; i++) {
            if (i != candidate) {
                // Celebrity should not know anyone
                if (Knows(candidate, i)) {
                    return -1;
                }
                // Everyone should know the celebrity
                if (!Knows(i, candidate)) {
                    return -1;
                }
            }
        }
        
        return candidate;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - At most 3n calls to knows function
  • Space Complexity: O(1) - Only using constant extra space

Key Insights

  1. Elimination Strategy: If A knows B, A cannot be celebrity. If A doesn’t know B, B cannot be celebrity.
  2. Two Pointers: Most efficient approach with O(1) space
  3. Verification: Always verify the final candidate meets celebrity criteria
  4. Optimization: Two pointers approach minimizes calls to knows function

Edge Cases

  1. No Celebrity: [[true,false],[false,true]] → -1
  2. Single Person: n = 1 → 0
  3. All Know Each Other: [[true,true],[true,true]] → -1

Follow-up Questions

  1. Multiple Celebrities: What if there can be multiple celebrities?
  2. Partial Information: What if some knows() calls are expensive?
  3. Distributed System: How would you solve this in a distributed system?

Common Mistakes

  1. Not Verifying: Forgetting to verify the final candidate
  2. Wrong Elimination: Incorrectly eliminating candidates
  3. Edge Cases: Not handling cases with no celebrity

Interview Tips

  1. Clarify Requirements: Ask about celebrity definition and constraints
  2. Discuss Approaches: Mention both two pointers and stack approaches
  3. Optimize Calls: Focus on minimizing calls to knows function
  4. Handle Edge Cases: Discuss scenarios with no celebrity