C#: Very Easy Intuitive Solution using Stack with Explanation. (Accepted)


  • 0

    0_1522384013458_945cedd5-1d48-4432-8ed0-58545a7ceb8c-image.png
    Basic Idea:

    • Push all the celebrity candidates into a stack.
    • Pop off top two candidates from the stack, discard one candidate based on return status of Knows(A, B).
    • Push the remained candidate onto stack.
    • Repeat step 2 and 3 until only one person remains in the stack.
    • Check the remained candidate in stack doesn’t have acquaintance with anyone else.
    //The Knows API is defined in the parent class Relation.  
    //bool Knows(int a, int b);
    public class Solution : Relation {
        public int FindCelebrity(int n) {
            if (n < 2) return n;
            Stack<int> allCelebrityCandidates = new Stack<int>();
            for (int i = 0; i < n; i++)
                allCelebrityCandidates.Push(i);                       
            while (allCelebrityCandidates.Count > 1) {
                int firstCandidate = allCelebrityCandidates.Pop();
                int secondCandidate = allCelebrityCandidates.Pop();
                if (Knows(firstCandidate, secondCandidate)) 
                    allCelebrityCandidates.Push(secondCandidate);
                else 
                    allCelebrityCandidates.Push(firstCandidate);
            }
            int possibleCelebrity = allCelebrityCandidates.Pop();
            for (int i = 0; i < n; i++) {  
                if (i == possibleCelebrity)
                    continue;
                bool possibleCelebrityKnowsSomeone = Knows(possibleCelebrity, i);
                bool someoneKnowsPossibleCelebrity = Knows(i, possibleCelebrity);
                if (possibleCelebrityKnowsSomeone || !someoneKnowsPossibleCelebrity) return -1
            }
            return possibleCelebrity;
        }
    }
    

Log in to reply
 

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