# Different Idea with explanation - O(nlogn) time - O(n) space

• I see there are `O(n)` time `O(1)` space solutions that are obviously better, but I think this is a very intuitive and interesting solution.

At first, everyone is a potential celebrity. We loop all celebs and make a check, we know that every call to `knows(a,b)` will give us one information: either `a` or `b` is not a potential celebrity and we can remove him. So after `n` checks we reduce the set size by half. So we have to loop the set `logn` times until it's size is 1.

In the end, we have only one candidate left. We check whether he, in fact, does not know anyone and no one knows him.

``````    public int findCelebrity(int n) {
Set<Integer> celeb = new HashSet<>();
for (int i=0; i < n; i++) {
}
while (celeb.size() > 1) {
Iterator<Integer> iter = celeb.iterator();
int a = iter.next();
int b = iter.next();
if(knows(a, b)) {
celeb.remove(a);
} else {
celeb.remove(b);
}
}
int theCeleb = celeb.iterator().next();
for (int i=0; i < n; i++) {
if (i != theCeleb) {
if (!knows(i, theCeleb)) return -1;
if (knows(theCeleb, i)) return -1;
}
}
return theCeleb;
}
``````

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