**Special thanks to @czonzhu**

The basic idea are as the following two steps:

```
1. As the celebrity knows no one else, switch the candidate if candidate knows i
2. Validate the candidate with: 1) !knows(candidate, i); 2) knows(i, candidate)
```

**Time complexity = O(n)**

```
public int findCelebrity(int n) {
int candidate = 0;
for (int i = 1; i < n; i++) {// As the celebrity knows no one else, switch the candidate if candidate knows i
if (knows(candidate, i))
candidate = i;
}
for (int i = 0; i < n; i++) {// Validate the candidate with: 1) !knows(candidate, i); 2) knows(i, candidate)
if (i != candidate && (knows(candidate, i) || !knows(i, candidate)))
return -1;
}
return candidate;
}
```