Yet another Two Pass solution.. Easier to understand maybe?


  • 0
    D

    Re: Java Solution. Two Pass

    How is this?

        public int findCelebrity(int n) {
            
            // first attempt to find a node with no out links from left to right
            // may end up in the LAST node which may not be celebrity (no way to check it in this direction)
            int target = 0;
            for(int i=0; i<n; i++) {
                if(knows(target, i)) {
                    target = i;
                }
            }
            
            // Then attempt to find a node with no out links from right to left
            // may end up in the FIRST node which may not be celebrity (no way to check it in this direction)
            int target2 = n-1;
            for(int i=n-2; i>=0; i--) {
                if(knows(target2, i)) {
                    target2 = i;
                }
            }
    
            // If a celebrity exists, the two pass must yield the same conclusion
            return target==target2? target : -1;
        }
    

    beats 99.77% : )


Log in to reply
 

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