Find the Celebrity

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 305 ms)

Metric	Value
Runtime	305 ms
Memory	42.3 MB
Date	2022-02-08

Solution

/* 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) {
        Stack<int> s = new Stack<int>();
        for(int i=0;i<n;i++)
        {
            s.Push(i);
        }
        
        int a = 0, b = 0;
        while(s.Count > 1)
        {
            a = s.Pop();
            b = s.Pop();
            if(Knows(a,b))
                s.Push(b);
            else s.Push(a);
        }
        int c = s.Pop();
        for(int i = 0;i<n;i++)
        {
            if(i==c) continue;
            if(!Knows(i,c) || Knows(c,i)) return -1;
        }
        
        return c; 
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed