
### Problem Statement

###### Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

###### Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

###### You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

###### There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

**INPUT**

- **[[1,1,0],[0,1,0],[1,1,1]]**

**OUTPUT**

- **1**

**EXPLANATION**

- As we can see in the 2nd array the 2nd person does not know 1st and 3rd person , but 1st and 3rd person knows 2nd.That makes 2nd person celebrity.

**Steps To Solve**

- As we know their can be only one celebrity , we can solve this problem by the process of elimination.
- First we will create a stack and push all the person in the stack.
- Then we pop the last two person from the stack(say person A and B) and ask if B knows A.
- If B knows A then we know B can't be a celebrity , hence we discard B and push A into the stack again.
- We will repeat the process untill one person is left in the stack.
- The last person in the stack will be our potential celebrity.
- Lastly, we will run a single loop and check all the conditions for that single person and return the result accordingly.
- Because we only compared the potential candidate (say X) once, we don’t know the relationship between X and other numbers. Since there can be no celebrity, maybe X is not.
- We trust X to be a celebrity just because other numbers are definitely not .
- Moving on to solution...

```js
function knows(a, b) {
  return input[a][b] === 1;
}
function findCelebrity(n) {
  const stack = [];

  for (let i = 0; i < n; i++) {
    stack.push(i);
  }

  while (stack.length >= 2) {
    const a = stack.pop();
    const b = stack.pop();

    if (knows(a, b)) {
      stack.push(b);
    } else {
      stack.push(a);
    }
  }

  const potentialCelebrity = stack.pop();

  for (let i = 0; i < n; i++) {
    if (i !== potentialCelebrity) {
      if (!knows(i, potentialCelebrity) || knows(potentialCelebrity, i)) {
        return -1;
      }
    }
  }

  return potentialCelebrity;
}
```

###### Time and Space Complexity

Time Complexity is **O(N)**.

Space complexity in this case is **O(1)**.
