277. Find the Celebrity - Detailed Explanation

Problem Statement

Imagine there is a party with n people labeled from 0 to n-1. A celebrity is defined as someone who:

• Is known by everyone else.
• Does not know any other person.

You are given a helper function:

boolean knows(int a, int b);

which returns true if person a knows person b, and false otherwise.

Task:
Find the celebrity if one exists; otherwise, return -1.

Example 1:

• Input: n = 3, with the following relationship (where a 1 indicates that person i knows person j):
  • Person 0: knows [0, 1, 0]
  • Person 1: knows [0, 0, 0] (celebrity candidate, because they know no one)
  • Person 2: knows [1, 1, 0]
• Output: 1
• Explanation: Everyone (0 and 2) knows person 1, and person 1 does not know anyone else.

Example 2:

• Input: n = 3, with relationships:
  • Person 0: knows [0, 1, 0]
  • Person 1: knows [1, 0, 0]
  • Person 2: knows [0, 1, 0]
• Output: -1
• Explanation: There is no person who is known by everyone and who knows no one.

Constraints:

• n is in the range [1, 100].
• There is at most one celebrity in the party.
• Minimize the number of calls to knows(a, b) since each call is considered expensive.

Hints to Approach the Problem

1. Elimination Idea:
   Notice that if person A knows person B, then A cannot be a celebrity. Conversely, if A does not know B, then B cannot be a celebrity. Use this observation to eliminate candidates.

2. Candidate Selection:
   You can start with a candidate (say, person 0) and iterate over the rest of the people. If the current candidate knows person i, then candidate cannot be a celebrity and you set candidate to i. After one pass, you will have a potential candidate; then, verify this candidate against all people.

Approaches to Solve the Problem

Approach 1: Brute Force

Idea:
For each person, check if:

• They do not know anyone else.
• Every other person knows them.

Method:
For every candidate i:

• For every other person j (j ≠ i):
  • If knows(i, j) is true or knows(j, i) is false, then i cannot be the celebrity.

Drawbacks:

• The brute-force method requires checking each pair, leading to O(n²) calls to knows().

Approach 2: Two-Pass Candidate Elimination (Optimal)

Idea:

1. First Pass (Candidate Selection):
   • Start with candidate = 0.
   • Iterate through all persons from 1 to n-1.
   • If candidate knows i, then candidate cannot be a celebrity. Set candidate = i.
2. Second Pass (Validation):
   • Verify that the candidate does not know anyone else.
   • Ensure every other person knows the candidate.

Advantages:

• This approach reduces the number of calls to knows() to O(n) in both passes.

Code Implementation

Python Code