Find the Celebrity - Practice Coding Problems

Find the Celebrity - 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 the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. You are only allowed to ask questions like: "Hi, A. Do you know B?" to get information about 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 an integer n and a helper function bool knows(a, b) that tells you whether a knows b. Implement a function int findCelebrity(n).

There will be exactly one celebrity if they are at the party. Return the celebrity's label if there is a celebrity at the party. If there is no celebrity, return -1.

Note: The n x n 2D array graph given as input is not directly available to you, and instead only accessible through the helper function knows. graph[i][j] == 1 represents person i knows person j, whereas graph[i][j] == 0 represents person i does not know person j.

Input & Output

Example 1 — Celebrity Exists

$ Input: n = 3, graph = [[1,1,0],[0,1,0],[1,1,1]]

› Output: 1

💡 Note: Person 1 is the celebrity: Person 0 knows 1, Person 2 knows 1, but Person 1 only knows themselves (diagonal doesn't count)

Example 2 — No Celebrity

$ Input: n = 2, graph = [[1,1],[1,1]]

› Output: -1

💡 Note: Both people know each other, so neither can be a celebrity (celebrity should know nobody)

Example 3 — Single Person

$ Input: n = 1, graph = [[1]]

› Output: 0

💡 Note: With only one person, they are trivially the celebrity (knows no one else, everyone else knows them - vacuous truth)

Constraints

1 ≤ n ≤ 100
graph.length == n
graph[i].length == n
graph[i][j] is 0 or 1
graph[i][i] == 1

Visualization

Tap to expand

Understanding the Visualization

Input

n people and adjacency matrix showing who knows whom

Process

Use elimination strategy to find candidate, then verify

Output

Return celebrity's ID or -1 if no celebrity exists

Key Takeaway

🎯 Key Insight: Each knows() call eliminates exactly one person, leading to optimal O(n) solution

Asked in

f Facebook 25 G Google 18 a Amazon 15 M Microsoft 12

The key insight is that each knows() call can eliminate exactly one person as a potential celebrity. The best approach uses single pass elimination followed by verification. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Elimination	O(n)	O(1)	Eliminate candidates in one forward pass, then verify the final candidate
Brute Force Check All	O(n²)	O(1)	Check every person by asking all other people about them
Two Pointers Elimination	O(n)	O(1)	Use two pointers to eliminate candidates, then verify the remaining one

Single Pass Elimination — Algorithm Steps

Step 1: Start with candidate = 0
Step 2: For each person i from 1 to n-1
Step 3: If candidate knows i, set candidate = i
Step 4: After loop, verify if candidate is actual celebrity

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

candidate = 0, check against person 1

Eliminate

If candidate knows someone, they become new candidate

Verify

Check final candidate against all people

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Simulate knows function based on graph
int knows(int a, int b, int graph[][100]) {
    return graph[a][b] == 1;
}

int solution(int n, int graph[][100]) {
    // Phase 1: Find candidate using elimination
    int candidate = 0;
    
    for (int i = 1; i < n; i++) {
        if (knows(candidate, i, graph)) {
            candidate = i; // Current candidate knows i, so candidate = i
        }
    }
    
    // Phase 2: Verify the candidate
    for (int i = 0; i < n; i++) {
        if (i != candidate) {
            // Candidate should not know anyone
            if (knows(candidate, i, graph)) {
                return -1;
            }
            // Everyone should know candidate
            if (!knows(i, candidate, graph)) {
                return -1;
            }
        }
    }
    
    return candidate;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int graph[100][100];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    
    printf("%d\n", solution(n, graph));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

One pass to eliminate O(n) + one pass to verify O(n) = O(n) total

✓ Linear Growth

Space Complexity

O(1)

Only using candidate variable for tracking

✓ Linear Space

89.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Elimination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler