277. Find the celebrity

Solution

Two pass
first find the candidate
second check the candidate

suppose k is candidate, in the first pass, when candidate encounters k, candidate must switch to k.

Complexity

O(N) O(1)

Code

/* 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 candidate = 0;
        for(int i = 1; i < n ;i++){
            if(knows(candidate, i))
                candidate = i;
        }
        for(int i = 0; i < n; i++){
            if(candidate != i){
                if(!(knows(i, candidate) && !knows(candidate, i)))
                    return -1;
            }
        }
        return candidate;
    }
}