My solution with min `knows` calls.

• Two round traversal algorithm, I using `S`/`celebrityNotknow` to mark the people that relationship is already clear to minimize the function calls.

``````int findCelebrity(int n) {
if(n == 1) return -1;
int celebrityNotKnow = 0;
unordered_set<int> S;
int celebrity = 0;
for(int i = 1; i < n; ++i) {
if(!knows(i, celebrity)) {
celebrityNotKnow = celebrity;
celebrity = i;
S.clear();
} else {
S.insert(i);
}
}
for(int i = 0; i < n; ++i) {
if(i == celebrity) continue;
if(i != celebrityNotKnow) {
if(knows(celebrity, i)) return -1;
}
if(!S.count(i)) {
if(!knows(i, celebrity)) return -1;
}
}
return celebrity;
}``````

• The Set is not necessary just save the next index: - I use `check` instead of `S`:

``````    if (n == 1) return -1;
//HashSet check = new HashSet();
int celeb = 0;
int notKnow = 0;
int check = 0;
for (int i = 1; i < n; i++) {
if (!knows(i, celeb)) {
notKnow = celeb;
celeb = i;
check = i + 1;
}
}

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

if (i == celeb) continue;
if (i != notKnow) {
if (knows(celeb, i)) return -1;
}
if (i < check) {
if (!knows(i,celeb)) return -1;
}
}

return celeb;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.