# Celebrity Problem using Stack

## Celebrity Problem using Stack

The Celebrity Problem involves finding the celebrity in a group of people. A celebrity is defined as someone who is known by everyone but knows no one. This can be efficiently solved using a stack by leveraging the relationships among people.

## Step-by-Step Process

Consider a group of people represented by a matrix where `knows(a, b)`

returns True if person `a`

knows person `b`

and False otherwise. To find the celebrity using a stack, follow these steps:

**Initialize a Stack**: Push all the people onto the stack.**Eliminate Non-Celebrities**: While there is more than one person in the stack, pop two people and use the`knows`

function to determine which one cannot be a celebrity. Push the potential celebrity back onto the stack.**Verify the Celebrity**: After processing, the potential celebrity remains in the stack. Verify that this person is indeed a celebrity by checking if they do not know anyone else and everyone else knows them.

After performing these steps, if a celebrity exists, they will be identified.

```
Input: Matrix representing relationships
Output: Index of the celebrity or -1 if no celebrity exists
```

## Pseudo Code

```
Function find_celebrity(matrix, n):
# Initialize a stack and push all people onto it
stack = []
For i in range(n):
stack.append(i)
# Eliminate non-celebrities
While len(stack) > 1:
a = stack.pop()
b = stack.pop()
If knows(a, b):
stack.append(b)
Else:
stack.append(a)
# Verify the potential celebrity
c = stack.pop()
For i in range(n):
If i != c and (knows(c, i) or not knows(i, c)):
Return -1
Return c
```

## Python Program to Solve the Celebrity Problem Using Stack

```
def knows(a, b, matrix):
return matrix[a][b]
class Stack:
def __init__(self):
self.stack = []
def push(self, data):
self.stack.append(data)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
# Function to find the celebrity in a group of n people
def find_celebrity(matrix, n):
stack = Stack()
for i in range(n):
stack.push(i)
while stack.size() > 1:
a = stack.pop()
b = stack.pop()
if knows(a, b, matrix):
stack.push(b)
else:
stack.push(a)
if stack.is_empty():
return -1
c = stack.pop()
for i in range(n):
if i != c and (knows(c, i, matrix) or not knows(i, c, matrix)):
return -1
return c
# Example usage:
# Matrix representation:
# 0 1 2
# 0 0 1 0
# 1 0 0 0
# 2 1 1 0
matrix = [
[0, 1, 0],
[0, 0, 0],
[1, 1, 0]
]
n = len(matrix)
celebrity = find_celebrity(matrix, n)
if celebrity == -1:
print("No celebrity found")
else:
print(f"Celebrity is at index: {celebrity}")
# Output: Celebrity is at index: 1
```

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and getting the size of the stack. The find_celebrity function uses the stack to find the celebrity in a group of people represented by a matrix by eliminating non-celebrities and verifying the potential celebrity.