AC java O(n) time O(1) space solution with detailed explanation

  • 2
    public int findCelebrity(int n) {
        int celebrity = 0, ask = celebrity + 1;
    /*use this loop to get one potential celebrity*/
        while(ask < n){
    /*if a knows b, that means a cannot be a celebrity*/
                celebrity = ask;
                ask = ask + 1;
    /*if a doesn't know b, that means b cannot be a celebrity*/
                ask = ask + 1;
    /*check if the potential celebrity is a "real" celebrity*/
        for(int i = 0; i < n; i++){
            if(i == celebrity) continue;
    /*if there is anyone who doesn't know the celebrity or the celebrity knows someelss, then it cannot be a celebrity*/
            if(!knows(i,celebrity) || knows(celebrity,i)) return -1;
        return celebrity;


Log in to reply

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