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

[amandeep18feb]

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;
    }
}