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

  • 0

    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++)
            while (allCelebrityCandidates.Count > 1) {
                int firstCandidate = allCelebrityCandidates.Pop();
                int secondCandidate = allCelebrityCandidates.Pop();
                if (Knows(firstCandidate, secondCandidate)) 
            int possibleCelebrity = allCelebrityCandidates.Pop();
            for (int i = 0; i < n; i++) {  
                if (i == possibleCelebrity)
                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.