LeetCode : 277. Find the Celebrity

[congr]

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

[congr]

very tricky, O(N)

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

        for (int i = 0; i < n; i++) {
            if (candi == i) continue;

            if (knows(candi, i) || !knows(i, candi)) return -1;
        }

        return candi;
    }
}