277. Find the Celebrity

Problem Description

The given problem presents a scenario where you're at a party with n people, each labeled with a unique number between 0 and n - 1. Your goal is to identify a possible celebrity among them. A celebrity is defined by two conditions: first, every other person at the party knows the celebrity, and second, the celebrity does not know anyone else at the party.

Your tool is a function knows(a, b), which checks if person a knows person b. You need to use this function to determine who, if anyone, is the celebrity at the party. It is important to minimize the number of calls to the knows function, since your objective is to find the celebrity efficiently.

The output of your task is to return the unique label of the celebrity if one exists, or -1 if there is no celebrity present.

Intuition

To solve this problem, we take advantage of the unique characteristics of the celebrity:

Every person other than the celebrity must know the celebrity, which means if knows(a, b) is true, a cannot be the celebrity.
The celebrity does not know anyone else, which implies if knows(a, b) is false, b cannot be the celebrity.

Based on these points, we can iterate through the list of people at the party and use the knows function to determine potential candidates for being the celebrity. One way to find the celebrity is to assume the first person (labeled 0) is the celebrity and then check this assumption against every other person using knows. If the assumed celebrity knows another person, then the assumption is wrong, and the other person becomes the new candidate for the celebrity. This process continues until we finish checking everybody.

After we find a candidate through the first iteration, we need to verify two conditions to confirm the candidate is indeed the celebrity:

The candidate does not know any person. If the candidate knows any person, then the candidate cannot be the celebrity.
Every person knows the candidate. If there is any person who does not know the candidate, then the candidate cannot be the celebrity.

The iteration for verification ensures that these conditions are met. If both conditions are satisfied for the candidate, then the candidate is the celebrity. Otherwise, there is no celebrity at the party.

The solution capitalizes on these ideas, using the intuition that knowing a person instantly disqualifies one from being a celebrity and not being known by at least one person also leads to a disqualification.

Learn more about Graph and Two Pointers patterns.

Solution Approach

The implementation provided is a straightforward two-pass solution that uses a simple elimination approach to find the celebrity.

First Pass - Identifying a Celebrity Candidate:

In the first for loop, we start with an assumption that person 0 might be the celebrity. We iterate over the range from 1 to n. For each person i, we check if the current candidate (ans) knows person i using the knows(ans, i) function.

If knows(ans, i) is true, it means that ans cannot be the celebrity because a celebrity does not know anyone else. So we update the ans to be i since i is now a possible celebrity candidate.
If knows(ans, i) is false, we do nothing and move on. This is because ans still could be the celebrity, as not knowing i aligns with the definition of a celebrity.

By the end of this loop, the variable ans holds the label of the only person who could potentially be the celebrity, because anyone who was known by ans has been eliminated from contention.

Second Pass - Validating the Candidate:

Next, we perform a second for loop to verify that the candidate (held in ans) is indeed the celebrity. There are two checks we need to pass:

The candidate should not know any other person. This is checked by if knows(ans, i), where ans is the candidate and i is any other person's label. If the candidate knows any person i, we return -1 as this disqualifies them from being the celebrity.
Every other person must know the candidate. We check this by ensuring not knows(i, ans) is false, meaning person i knows ans. If we find someone who doesn't know ans, we return -1 as this also disqualifies ans from being the celebrity.

If both conditions are satisfied for all other people at the party, then we can safely conclude that ans is the celebrity and return their label. If either condition fails for any person, we return -1 to indicate that there is no celebrity.

There is no need for any additional data structure as we can keep track of the potential celebrity with a single variable ans. This approach is efficient because it requires at most 2*(n - 1) calls to knows — once to eliminate non-celebrities and once again to confirm that the remaining candidate is indeed the celebrity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with 4 people at the party, where the unique labels for them are 0, 1, 2, and 3. Assume that person 3 is the celebrity according to the problem's definition. We want to identify this person using the solution approach described.

First Pass - Identifying a Celebrity Candidate:
- Initialize the candidate to person 0 (ans = 0). We'll check if person 0 is the celebrity.
- Check if 0 knows 1, using knows(0, 1). Let's say it returns false, so we do nothing because 0 could still be the celebrity.
- Check if 0 knows 2, using knows(0, 2). This time it returns true, which means 0 cannot be the celebrity. Update the candidate to person 2 (ans = 2).
- Check if 2 knows 3, using knows(2, 3). It returns false, so we do nothing; 2 is still a potential celebrity.
By the end of the first pass, our candidate is person 2.
Second Pass - Validating the Candidate:
- We need to verify if 2 is truly the celebrity by doing two checks: does not know anyone else (knows(ans, i)) and is known by everyone else (knows(i, ans)).
- Check if 2 knows 0, 1, or 3, using knows(2, 0), knows(2, 1), and knows(2, 3). They all should return false. Let's say they do, so 2 passes the first check.
- Next, we need to check if all others (0, 1, 3) know 2. We check knows(0, 2), knows(1, 2), and knows(3, 2). They all should return true for 2 to be the celebrity. Let's say knows(0, 2) is true, knows(1, 2) is true, but knows(3, 2) is false because the celebrity (3) should not know anyone else.
Person 2 fails the second check because the celebrity (3) does not know them.

We will need to continue the same check for other persons 0 and 1:
- Person 0 knows 2, so 0 is not a celebrity.
- Person 1 knows 2, so 1 is not a celebrity.
Finally, when it comes to person 3, the checks are as follows:
- 3 does not know 0, 1, or 2, fulfilling the first condition of being a celebrity.
- All persons 0, 1, and 2 know 3, fulfilling the second condition.
By the end of the verification process, we determine that person 3 meets both conditions, and since no other person does, we conclude that the label of the celebrity is 3. If the checks had failed for 3 as they did for 2, then we would return -1, indicating no celebrity is present. However, in this case, we return 3 as the label of the celebrity at the party.

Solution Implementation

1# The knows API is already defined for you.
2# Returns a boolean, indicating whether person a knows person b.
3# def knows(a: int, b: int) -> bool:
4
5class Solution:
6    def findCelebrity(self, n: int) -> int:
7        # Initialize the candidate for celebrity to 0
8        candidate = 0
9        # Iterate over the range from 1 to n-1
10        for i in range(1, n):
11            # If the candidate knows person i, then switch candidate to i
12            if knows(candidate, i):
13                candidate = i
14
15        # Verify candidate is indeed a celebrity
16        for i in range(n):
17            # Make sure we skip comparing the candidate with themselves
18            if candidate != i:
19                # Candidate should not know anyone, and everyone should know the candidate
20                if knows(candidate, i) or not knows(i, candidate):
21                    # If the condition fails, return -1 because there is no celebrity
22                    return -1
23      
24        # If all checks pass, return the candidate as the celebrity
25        return candidate
26

1/* The knows API is defined in the parent class Relation.
2      boolean knows(int a, int b); */
3
4public class Solution extends Relation {
5    /**
6     * Determine the celebrity by knockout method
7     *
8     * @param n Number of people in the party
9     * @return The index of the celebrity if exists, otherwise return -1
10     */
11    public int findCelebrity(int n) {
12        // Initial assumption: the first person (0) may be the celebrity
13        int candidate = 0;
14
15        // First Pass: Find a candidate for celebrity
16        for (int i = 1; i < n; ++i) {
17            // If the candidate knows i, candidate cannot be a celebrity, thus i might be
18            if (knows(candidate, i)) {
19                candidate = i;
20            }
21        }
22
23        // Second Pass: Verify the candidate is really a celebrity
24        for (int i = 0; i < n; ++i) {
25            // Skip if i is the same as the candidate
26            if (candidate != i) {
27                // If the candidate knows i, or i doesn't know the candidate, 
28                // then the candidate cannot be a celebrity
29                if (knows(candidate, i) || !knows(i, candidate)) {
30                    return -1;
31                }
32            }
33        }
34
35        // If all checks pass, the candidate is a celebrity
36        return candidate;
37    }
38}
39

1/* The knows API is defined for you.
2      bool knows(int a, int b); */
3
4class Solution {
5public:
6    // This method is to find the celebrity within 'n' people. 
7    // A celebrity is defined as somebody who everyone knows but who knows nobody themselves.
8    int findCelebrity(int n) {
9        // Initialize the candidate for celebrity to 0
10        int candidate = 0;
11
12        // The first loop is to find a candidate who might be the celebrity.
13        for (int i = 1; i < n; ++i) {
14            // If the candidate knows 'i', then 'candidate' can't be a celebrity.
15            // 'i' might be the celebrity.
16            if (knows(candidate, i)) {
17                candidate = i;
18            }
19        }
20
21        // The second loop is to confirm whether the candidate is the celebrity.
22        for (int i = 0; i < n; ++i) {
23            // The candidate should not know any other person,
24            // and all other people should know the candidate.
25            // If these conditions are not met, return -1 indicating no celebrity.
26            if (candidate != i && (knows(candidate, i) || !knows(i, candidate))) {
27                return -1;
28            }
29        }
30
31        // If all conditions are met, return the candidate as the celebrity.
32        return candidate;
33    }
34};
35

1// TypeScript function representing the knows API
2// It should return true if person a knows person b, false otherwise.
3declare function knows(a: number, b: number): boolean;
4
5// This function finds the celebrity within 'n' people.
6// A celebrity is someone whom everyone knows but who knows no one themselves.
7function findCelebrity(n: number): number {
8    // Initialize the candidate for the celebrity to 0
9    let candidate: number = 0;
10
11    // The first loop is to find a candidate who might be the celebrity.
12    for (let i = 1; i < n; i++) {
13        // If the candidate knows 'i', then 'candidate' cannot be the celebrity.
14        // In this case, 'i' might be the new candidate.
15        if (knows(candidate, i)) {
16            candidate = i;
17        }
18    }
19
20    // The second loop is to confirm whether the candidate is the celebrity.
21    for (let i = 0; i < n; i++) {
22        // The candidate should not know any other person,
23        // and all other people should know the candidate.
24        // If these conditions are not met, return -1 indicating there is no celebrity.
25        if (candidate !== i && (knows(candidate, i) || !knows(i, candidate))) {
26            return -1;
27        }
28    }
29
30    // If all conditions are met, return the candidate as the celebrity.
31    return candidate;
32}
33

Time and Space Complexity

Time Complexity

The given Python code is comprised of two separate for loops that are not nested.

The first for loop runs from 1 to n-1 and involves a constant amount of work for each iteration, i.e., one call to the knows API function. This loop determines the candidate for the celebrity.

The second for loop checks whether the found candidate is actually a celebrity by making sure that everyone knows the candidate and the candidate knows no one (except themselves, which is not checked). This loop makes up to 2*(n-1) calls to the knows API.

Therefore, the time complexity for the code is O(n) + O(n), which simplifies to O(n).

Space Complexity

The code uses a fixed amount of extra space (only variable ans is used to store the celebrity candidate). It does not allocate any space that is dependent on the input size n.

Thus, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know