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:

1. Initialize a Stack: Push all the people onto the stack.
2. 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.
3. 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.