277. Find the Celebrity

The idea is, first of all find the candidate first. And then verify the candidate. The key point here is the invariant that if everybody from [celebrity+1, n-1] must know the celebrity. If the invariant breaks, then the breaking one must be a candidate for the celebrity. And then in the second loop, we check whether the candidate is a valid celebrity.

1:  // Forward declaration of the knows API.  
2:  bool knows(int a, int b);  
3:  class Solution {  
4:  public:  
5:    int findCelebrity(int n) {  
6:      int candidate = 0;  
7:      for (int i = 1; i < n; i++) {  
8:        if (!knows(i, candidate)) candidate = i;  
9:      }  
10:      for (int i = 0; i < n; i++) {  
11:        if (candidate != i && (knows(candidate, i) || !knows(i, candidate))) return -1;  
12:      }  
13:      return candidate;  
14:    }  
15:  };