Skip to content

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;

    // The 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;

    // The 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.
# Returns 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

    # The 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