LeetCode 277: Find the Celebrity Solution in Python – A Step-by-Step Guide

What Is LeetCode 277: Find the Celebrity?

In LeetCode 277: Find the Celebrity, you’re given an integer n (number of people) and a helper function knows(a, b) that returns True if person a knows person b, False otherwise. Your task is to find the celebrity—defined as someone everyone knows but who knows no one—or return -1 if no celebrity exists. For example, with n = 3 and a matrix where person 1 is known by all and knows no one, the celebrity is 1. This problem tests your ability to optimize queries in a directed graph, connecting to concepts in LeetCode 323: Number of Connected Components in an Undirected Graph.

Problem Statement

• Input:
• Integer n (number of people, 0 to n-1).
• API knows(a, b): Returns boolean (True if a knows b).
• Output: Integer—celebrity’s ID (0 to n-1) or -1 if none.
• Rules:
• Celebrity: Everyone knows them, they know no one.
• Only one celebrity possible, or none.
• Minimize calls to knows().

Constraints

• 2 <= n <= 100

Examples

• Input: n = 3, knows() matrix:

[[1,1,0], [0,1,0], [1,1,1]]

• Output: 1 (Everyone knows 1, 1 knows no one)

[[1,1], [1,1]]

• Output: -1 (No celebrity: both know each other)

[[1,0], [0,1]]

• Output: -1 (No celebrity: neither knows all)

Understanding the Problem: Spotting the VIP

To solve LeetCode 277: Find the Celebrity in Python, we need to identify a person who is known by all (n-1 others know them) and knows no one (they know 0 others), using the knows(a, b) API efficiently. A naive approach—checking every person fully—takes O(n²) calls, too many for n up to 100. We’ll use:

• Best Solution (Two-Pass Elimination): O(n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force): O(n²) time, O(1) space—clear but inefficient.

Let’s start with the two-pass elimination solution, explained in a beginner-friendly way.

Best Solution: Two-Pass Elimination Approach

Why This Is the Best Solution

The two-pass elimination approach is the top choice for LeetCode 277 because it’s efficient—O(n) time, O(1) space—and minimizes API calls by first narrowing down a candidate, then verifying them. It uses the logical property that a non-celebrity knowing someone eliminates them, cutting the search space cleverly. It’s like playing a social deduction game with a sharp strategy—smart and quick!

How It Works

Think of this as a VIP eliminator:

• Step 1: Find Candidate (Pass 1):
• Start with candidate = 0.
• For i from 1 to n-1:
• If candidate knows i, candidate = i (eliminate old candidate).
• If not, keep candidate (i isn’t celebrity if candidate doesn’t know them).
• Step 2: Verify Candidate (Pass 2):
• Check if candidate knows anyone (should be 0).
• Check if everyone knows candidate (should be n-1).
• Step 3: Return Result:
• Candidate if verified, -1 if not.
• Step 4: Why It Works:
• Pass 1: If A knows B, A isn’t celebrity; if A doesn’t know B, B isn’t either.
• Pass 2: Confirms candidate meets both conditions.

It’s like narrowing down suspects with a single sweep!

Step-by-Step Example

Example: n = 3, Matrix:

Copy code[[1,1,0],
 [0,1,0],
 [1,1,1]]

• Pass 1: Candidate = 0
• i=1: knows(0,1)=1, candidate = 1
• i=2: knows(1,2)=0, candidate = 1 (2 eliminated)
• Pass 2: Verify candidate 1
• Knows no one: knows(1,0)=0, knows(1,2)=0, True
• Everyone knows: knows(0,1)=1, knows(2,1)=1, True (self doesn’t count)
• Result: 1

Example: n = 2, Matrix:

Copy code[[1,0],
 [0,1]]

• Pass 1: Candidate = 0, knows(0,1)=0, candidate = 0
• Pass 2:
• Knows no one: knows(0,1)=0, True
• Everyone knows: knows(1,0)=0, False
• Result: -1

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def findCelebrity(self, n: int) -> int:
        # Pass 1: Find candidate
        candidate = 0
        for i in range(1, n):
            if knows(candidate, i):
                candidate = i  # If candidate knows i, i becomes candidate

        # Pass 2: Verify candidate
        for i in range(n):
            if i != candidate:
                # Candidate must not know i, and i must know candidate
                if knows(candidate, i) or not knows(i, candidate):
                    return -1

        return candidate

• Lines 4-7: Pass 1:
• Start with candidate 0.
• If candidate knows i, update candidate to i.
• Lines 10-14: Pass 2:
• For each i ≠ candidate:
• Check knows(candidate, i)=False (knows no one).
• Check knows(i, candidate)=True (known by all).
• Time Complexity: O(n)—two linear passes.
• Space Complexity: O(1)—single variable.

This is like a celebrity-spotting sleuth—fast and sleek!

Alternative Solution: Brute Force Approach

Why an Alternative Approach?

The brute-force approach—O(n²) time, O(1) space—checks every person as a potential celebrity by verifying both conditions (known by all, knows none) exhaustively. It’s the simplest way to grasp the problem but makes far more API calls than needed. It’s like asking everyone about everyone—clear but slow!

How It Works

Check each person:

• Step 1: For each i from 0 to n-1:
• Verify i knows no one (n-1 checks).
• Verify all know i (n-1 checks).
• Step 2: Return i if valid, -1 if none.

Step-by-Step Example

Example: n = 3, Matrix:

Copy code[[1,1,0],
 [0,1,0],
 [1,1,1]]

• i=0: knows(0,1)=1, not a celebrity
• i=1: knows(1,0)=0, knows(1,2)=0; knows(0,1)=1, knows(2,1)=1, celebrity
• i=2: knows(2,0)=1, not a celebrity
• Result: 1

Code for Brute Force Approach

Copy codeclass Solution:
    def findCelebrity(self, n: int) -> int:
        for i in range(n):
            is_celebrity = True
            # Check if i knows anyone
            for j in range(n):
                if i != j and knows(i, j):
                    is_celebrity = False
                    break
            # Check if everyone knows i
            if is_celebrity:
                for j in range(n):
                    if j != i and not knows(j, i):
                        is_celebrity = False
                        break
            if is_celebrity:
                return i
        return -1

• Time Complexity: O(n²)—two nested loops per person.
• Space Complexity: O(1)—no extra space.

It’s a thorough people-checker—vivid but slow!

Comparing the Two Solutions

• Two-Pass Elimination (Best):
• Pros: O(n) time, O(1) space, fast and minimal calls.
• Cons: Logic less obvious.
• Brute Force (Alternative):
• Pros: O(n²) time, O(1) space, straightforward.
• Cons: Too many API calls.

Two-pass wins for efficiency.

Additional Examples and Edge Cases

• n=1: -1 (no celebrity possible).
• n=2, [[1,0],[1,0]]: 1.
• n=3, all know all: -1.

Both handle these, but two-pass is faster.

Complexity Breakdown

• Two-Pass Elimination: Time O(n), Space O(1).
• Brute Force: Time O(n²), Space O(1).

Two-pass is the clear choice.

Key Takeaways

• Two-Pass Elimination: Narrow and verify—efficient!
• Brute Force: Check all—clear!
• Python: Logic and loops shine—see [Python Basics](/python/basics).
• Graphs: Elimination beats brute force.

Final Thoughts: Spot the Star

LeetCode 277: Find the Celebrity in Python is a graph-based optimization gem. The two-pass elimination solution offers speed and elegance, while brute force provides a tangible baseline. Want more graph challenges? Try LeetCode 323: Number of Connected Components in an Undirected Graph or LeetCode 547: Number of Provinces. Ready to find the VIP? Head to Solve LeetCode 277 on LeetCode (premium) and spot that celebrity today!