AC Java solution using stack


  • 45
    public int findCelebrity(int n) {
        // base case
        if (n <= 0) return -1;
        if (n == 1) return 0;
        
        Stack<Integer> stack = new Stack<>();
        
        // put all people to the stack
        for (int i = 0; i < n; i++) stack.push(i);
        
        int a = 0, b = 0;
        
        while (stack.size() > 1) {
            a = stack.pop(); b = stack.pop();
            
            if (knows(a, b)) 
                // a knows b, so a is not the celebrity, but b may be
                stack.push(b);
            else 
                // a doesn't know b, so b is not the celebrity, but a may be
                stack.push(a);
        }
        
        // double check the potential celebrity
        int c = stack.pop();
        
        for (int i = 0; i < n; i++)
            // c should not know anyone else
            if (i != c && (knows(c, i) || !knows(i, c)))
                return -1;
        
        return c;
    }

  • 0
    A

    @jeantimex what's the time complexity?


  • 1
    M

    @ayxyz In the first for loop, you are decreasing the stack size by half every loop, that's 2n. In the second loop, another n. Total (3n) running time, call to 'knows'. Agreed?


Log in to reply
 

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