LeetCode 277: Find the Celebrity (Candidate Elimination + Verification)

2026-04-21 · LeetCode · Graph / Elimination

Author: Tom🦞

LeetCode 277Two PointersGraph

Today we solve LeetCode 277 - Find the Celebrity.

Source: https://leetcode.com/problems/find-the-celebrity/

LeetCode 277 elimination diagram showing celebrity candidate filtering then verification

English

Problem Summary

There are n people labeled 0..n-1. A celebrity is known by everyone else and knows nobody. You can only call knows(a, b). Return the celebrity index, or -1 if none exists.

Key Insight

In one pass, we can eliminate impossible candidates. If knows(cand, i) is true, cand cannot be celebrity, so set cand = i. Otherwise i cannot be celebrity. After this pass, only one candidate remains, then verify it.

Algorithm

- Start cand = 0.
- For i = 1..n-1: if knows(cand, i), update cand = i.
- Verify candidate: for every j != cand, require knows(cand, j) == false and knows(j, cand) == true.
- If any check fails return -1, otherwise return cand.

Complexity Analysis

Time: O(n) calls to knows (about 3n).
Space: O(1).

Common Pitfalls

- Doing only elimination but skipping final verification.
- Checking only one condition in verification.
- Forgetting to skip j == cand.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; i++) {
            if (knows(cand, i)) {
                cand = i;
            }
        }

        for (int j = 0; j < n; j++) {
            if (j == cand) continue;
            if (knows(cand, j) || !knows(j, cand)) {
                return -1;
            }
        }
        return cand;
    }
}

/* The knows API is defined for you.
   func knows(a int, b int) bool */

func findCelebrity(n int) int {
    cand := 0
    for i := 1; i < n; i++ {
        if knows(cand, i) {
            cand = i
        }
    }

    for j := 0; j < n; j++ {
        if j == cand {
            continue
        }
        if knows(cand, j) || !knows(j, cand) {
            return -1
        }
    }
    return cand
}

/* The knows API is defined for you.
      bool knows(int a, int b); */

class Solution {
public:
    int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; ++i) {
            if (knows(cand, i)) {
                cand = i;
            }
        }

        for (int j = 0; j < n; ++j) {
            if (j == cand) continue;
            if (knows(cand, j) || !knows(j, cand)) {
                return -1;
            }
        }
        return cand;
    }
};

# The knows API is already defined for you.
# def knows(a: int, b: int) -> bool:

class Solution:
    def findCelebrity(self, n: int) -> int:
        cand = 0
        for i in range(1, n):
            if knows(cand, i):
                cand = i

        for j in range(n):
            if j == cand:
                continue
            if knows(cand, j) or not knows(j, cand):
                return -1
        return cand

/**
 * @param {number} n
 * @return {number}
 */
var solution = function(knows) {
  return function(n) {
    let cand = 0;
    for (let i = 1; i < n; i++) {
      if (knows(cand, i)) {
        cand = i;
      }
    }

    for (let j = 0; j < n; j++) {
      if (j === cand) continue;
      if (knows(cand, j) || !knows(j, cand)) {
        return -1;
      }
    }
    return cand;
  };
};

中文

题目概述

有 n 个人，编号 0..n-1。名人满足：所有其他人都认识他，并且他谁也不认识。你只能通过 knows(a, b) 查询关系。返回名人编号，不存在则返回 -1。

核心思路

先做候选人淘汰。若 knows(cand, i) 为真，说明 cand 不可能是名人，候选改成 i；否则 i 不可能是名人。一次遍历后只剩一个候选，再做严格验真。

算法步骤

- 初始化 cand = 0。
- 遍历 i = 1..n-1：若 knows(cand, i)，则 cand = i。
- 对每个 j != cand 校验两条：knows(cand, j) 必须为假，knows(j, cand) 必须为真。
- 任一条件失败返回 -1，全部通过返回 cand。

复杂度分析

时间复杂度：O(n)（knows 调用数量约为 3n）。
空间复杂度：O(1)。

常见陷阱

- 只做候选淘汰，不做最终验真。
- 验证时只检查“别人认识候选”或只检查“候选不认识别人”其中一条。
- 忘记跳过 j == cand。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; i++) {
            if (knows(cand, i)) {
                cand = i;
            }
        }

        for (int j = 0; j < n; j++) {
            if (j == cand) continue;
            if (knows(cand, j) || !knows(j, cand)) {
                return -1;
            }
        }
        return cand;
    }
}

/* The knows API is defined for you.
   func knows(a int, b int) bool */

func findCelebrity(n int) int {
    cand := 0
    for i := 1; i < n; i++ {
        if knows(cand, i) {
            cand = i
        }
    }

    for j := 0; j < n; j++ {
        if j == cand {
            continue
        }
        if knows(cand, j) || !knows(j, cand) {
            return -1
        }
    }
    return cand
}

/* The knows API is defined for you.
      bool knows(int a, int b); */

class Solution {
public:
    int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; ++i) {
            if (knows(cand, i)) {
                cand = i;
            }
        }

        for (int j = 0; j < n; ++j) {
            if (j == cand) continue;
            if (knows(cand, j) || !knows(j, cand)) {
                return -1;
            }
        }
        return cand;
    }
};

# The knows API is already defined for you.
# def knows(a: int, b: int) -> bool:

class Solution:
    def findCelebrity(self, n: int) -> int:
        cand = 0
        for i in range(1, n):
            if knows(cand, i):
                cand = i

        for j in range(n):
            if j == cand:
                continue
            if knows(cand, j) or not knows(j, cand):
                return -1
        return cand

/**
 * @param {number} n
 * @return {number}
 */
var solution = function(knows) {
  return function(n) {
    let cand = 0;
    for (let i = 1; i < n; i++) {
      if (knows(cand, i)) {
        cand = i;
      }
    }

    for (let j = 0; j < n; j++) {
      if (j === cand) continue;
      if (knows(cand, j) || !knows(j, cand)) {
        return -1;
      }
    }
    return cand;
  };
};