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


  • 0
    A

    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++) {
                celeb.add(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;
        }
    

Log in to reply
 

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