Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity.

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

• Time: O(n)
• Space: O(1)

public int findCelebrity(int n) {
    int ret = 0;
    for (int i = 1; i < n; i++)
        if (knows(ret, i)) ret = i;
    for (int i = 0; i < n; i++) {
        if (i < ret && !knows(i, ret) || knows(ret, i)) return -1;
        if (i > ret && !knows(i, ret)) return -1;
    }
    return ret;
}

private boolean knows(int candidate, int i) {
    return false;
}