Find the celebrity

Two Pointers Graph Theory Interactive

48.9% acceptance

Mar 31, 2026

3002

320

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 that 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, wherease graph[i][j] == 0 represents person j does not know person i.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

/* The knows API is defined for you.
     knows(a: i32, b: i32)->bool;
  to call it use self.knows(a,b)
*/

impl Solution {
  pub fn find_celebrity(&self, n: i32) -> i32 {
    // First pass: find candidate
    let mut candidate = 0;
    for i in 1..n {
      if self.knows(candidate, i) {
        candidate = i;
      }
    }
    // Second pass: verify candidate
    for i in 0..n {
      if i != candidate {
        if self.knows(candidate, i) || !self.knows(i, candidate) {
          return -1;
        }
      }
    }
    candidate
  }
}