Problem

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

Examples

Example 1:

graph LR;
0 --> 1
2 --> 1
2 --> 0
style 1 fill:#FF9933
  
Input: n = 3
0 know 1
1 doesn't know 0

Output: 1
Explanation: Everyone knows 1,and 1 knows no one.

Solution

Method 1 - Brute force

To determine if each number i is a celebrity, we need to check all knows(i, j), where j ranges from 0 to n. If all knows(i, j) == 0 and knows(j, i) == 1 for all pairs, then i is a celebrity; otherwise, i is not a celebrity.

The time complexity T(n) is O(n^2) because we need to evaluate n numbers, and for each number, we must pair it with n-1 others. Another way to view this is by checking all n*n pairs of knows(i, j).

Method 2 - Linear Elimination

We know that there is one celebrity c with the two following properties –

  1. Everybody knows c
  2. c doesn’t know anybody

So, we can eliminate the need to check n*n pairs, because of it.

With one call knows(i, j) - we have 2 options - true or false -

  • If i knows j ⇨ knows(i,j) = true ⇨ i is not the celebrity because a celebrity knows no one. (rule 2). (j is potential candidate)
  • If i doesn’t know j ⇨ knows(i,j) = false ⇨ j is not the celebrity because everyone knows the celebrity. (rule 1) (i is potential candidate)

Each call to knows(i, j) results in either 0 or 1, allowing us to eliminate a non-celebrity candidate.

Algorithm

Here’s the algorithm based on this analysis:

  1. Base case: Start with i = 0, j = 1. Check knows(0, 1) to identify a potential candidate.
    • If knows(0, 1) = true, then j is the potential candidate.
    • If knows(0, 1) = false, then i is the potential candidate.
  2. Iterate through all numbers:
    • Use a loop to compare the candidate with the next number.
    • If knows(candidate, j) == 1, eliminate the current candidate and set candidate = j.
    • If knows(candidate, j) == 0, eliminate j and keep the current candidate.
    • By the end of the loop, you will have a final candidate X. If a celebrity exists, it must be X.
  3. Verify the final candidate:
    • Are we done yet? No. The final candidate say X is merely the best estimate. It’s crucial to verify if X is indeed the real celebrity.
    • Why? Because X was compared only once with others, we lack complete information about X’s relationships. There may be no celebrity at all, and X could fail the criteria. We trust X solely because other candidates were disqualified.
    • After determining the final candidate, verify to ensure everyone knows the candidate and the candidate knows no one.
    • If the candidate fails verification, return -1.

Complexity

  • ⏰ Time complexity: θ(n)
  • 🧺 Space complexity: O(1)

Visualizing this with a tree, each level adds a new number to compare with, so the height and time complexity is θ(n) i.e. in worst case, the recursive steps or iterative comparisons we perform grow linearly with the number of people, n.

Code

Java
public class Solution extends Relation {

	public int findCelebrity(int n) {
		// Step 1: Find the candidate
		int candidate = 0;

		for (int i = 1; i < n; i++) {
			if (knows(candidate, i)) {
				candidate = i;
			}
		}

		// Step 2: Verify the candidate
		for (int i = 0; i < n; i++) {
			if (candidate == i) {
				continue;
			}
			// if candidate knows some one - not celebrity
			// if someone doesn't know candidate - not celebrity	         
			if ((knows(candidate, i) || !knows(i, candidate))) {
				return -1; // Candidate is not a celebrity
			}
		}

		return candidate;
	}
}