```
int findCelebrity(int n) {
int candidate = 0;
for (int i = 1; i < n; i++) {
// if candidate knows i, only i will be a valid candidate in [0, i]
if (knows(candidate, i)) {
candidate = i;
}
}
// check the two way relation between candidate and the people bofore candidate
for (int i = 0; i < candidate; i++) {
if (knows(candidate, i) || !knows(i, candidate)) {
return -1;
}
}
// since we already know candidate doesn't know anyone after him, only need to check one way relation
for (int i = candidate + 1; i < n; i++) {
if (!knows(i, candidate)) {
return -1;
}
}
return candidate;
}
```