Leetcode 277: Find the Celebrity

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

Notes:

One way to think about this question is that: for each pair of (i, j), once we find i know j, or j doesn't know i, then i is not a celebrity. Otherwise, if i doesn't know j, but j knows i. Then j is not celebrity neither. See the code below:

bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        vector<bool> candidate(n, true);//memorize the results
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {//compare i with all the rest
                if (candidate[i] && i != j) {
                    if (knows(i, j) || !knows(j, i)) {
                        candidate[i] = false;
                        break;
                    } else {
                        candidate[j] = false;
                    }
                }
            }
            if (candidate[i]) return i;
        }
        return -1;
    }
};