# 277. Find the Celebrity

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int findCelebrity(int n) { int candidate = 0; // everyone knows the celebrity for (int i = 1; i < n; ++i) if (knows(candidate, i)) candidate = i; // candidate knows nobody and everyone knows the celebrity for (int i = 0; i < n; ++i) { if (i < candidate && knows(candidate, i) || !knows(i, candidate)) return -1; if (i > candidate && !knows(i, candidate)) return -1; } return candidate; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution extends Relation { public int findCelebrity(int n) { int candidate = 0; // everyone knows the celebrity for (int i = 1; i < n; ++i) if (knows(candidate, i)) candidate = i; // candidate knows nobody and everyone knows the celebrity for (int i = 0; i < n; ++i) { if (i < candidate && knows(candidate, i) || !knows(i, candidate)) return -1; if (i > candidate && !knows(i, candidate)) return -1; } return candidate; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 # The knows API is already defined for you. # return a bool, whether a knows b # def knows(a: int, b: int) -> bool: class Solution: def findCelebrity(self, n: int) -> int: candidate = 0 # everyone knows the celebrity for i in range(1, n): if knows(candidate, i): candidate = i # candidate knows nobody and everyone knows the celebrity for i in range(n): if i < candidate and knows(candidate, i) or not knows(i, candidate): return -1 if i > candidate and not knows(i, candidate): return -1 return candidate