## Coding Challenge – Celebrity Problem.

Celebrity is the person to whom everyone know but he do not know any person. This problem one of the programing problem that asked in companies

## Problem Statement:

You are going to a party of N people and your task is to find a celebrity in the party. Means Celebrity is know by N-1 person in the party of N people.

## Solution:

A Square matrix is used to represent the people in the party → if an element of row `i` and column `j `is set to 1 it means i-th person knows `j` else 0.

```Input:
MATRIX = { {0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0} }
Output: id = 2
Explanation: The person with ID 2 does not know anyone but everyone knows him

Input:
MATRIX = { {0, 0, 1, 0},
{0, 0, 1, 0},
{0, 1, 0, 0},
{0, 0, 1, 0} }
Output: No celebrity
Explanation: There is no celebrity.```

There are two ways to solve this problem

1. Using Stack
2. Using Graph

### Using Stack

• If A knows B, then A can’t be a celebrity. Discard A, and B may be celebrity.
• If A doesn’t know B, then B can’t be a celebrity. Discard B, and A may be celebrity.
• Repeat above two steps till there is only one person.
• Ensure the remained person is a celebrity.

#### Algorithm

1. Create a stack and push all the id’s in the stack.
2. Run a loop while there are more than 1 element in the stack.
3. Pop top two element from the stack (represent them as A and B)
4. If A knows B, then A can’t be a celebrity and push B in stack. Else if A doesn’t know B, then B can’t be a celebrity push A in stack.
5. Assign the remaining element in the stack as the celebrity.
6. Run a loop from 0 to n-1 and find the count of persons who knows the celebrity and the number of people whom the celebrity knows. if the count of persons who knows the celebrity is n-1 and the count of people whom the celebrity knows is 0 then return the id of celebrity else return -1.

#### Code

```MATRIX = [[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]]

def a_knows_b(a, b):
return MATRIX[a][b]

def find_celebrity_stack(guestCount):
# create a empty array which act as stack
stack = []
# push all guest in the stack (means all ids i.e 0 to guest count)
for i in range(guestCount):
stack.append(i)

while len(stack) > 1:
# now pick top two guest from stack
guestA = stack.pop()
guestB = stack.pop()
# check guestA knows guestB
# if guestA knows guestB then push back guestB into stack else push guestA
if a_knows_b(guestA, guestB):
stack.append(guestB)
else:
stack.append(guestA)

if not len(MATRIX):
return -1
celebrity = stack.pop()

# Now verify that last person in the stack is celebrity or not
for i in range(guestCount):
if i != celebrity and (a_knows_b(celebrity, i) or not a_knows_b(i, celebrity)):
return -1

return celebrity

print(find_celebrity_stack(len(MATRIX)))```

### Using Graph

Initialize indegree and outdegree of every vertex as 0. If A knows B, draw a directed edge from A to B, increase indegree of B and outdegree of A by 1.  If a celebrity is present in the party, there will be one sink node in the graph with outdegree of zero and indegree of N-1.

#### Algorithm

1. Create two arrays indegree and outdegree, to store the indegree and outdegree
2. Run a nested loop, the outer loop from 0 to n and inner loop from 0 to n.
3. For every pair i, j check if i knows j then increase the outdegree of i and indegree of j
4. For every pair i, j check if j knows i then increase the outdegree of j and indegree of i
5. Run a loop from 0 to n and find the id where the indegree is n-1 and outdegree is 0

### Code

```MATRIX = [[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]]

def a_knows_b(a, b):
return MATRIX[a][b]

def find_celebrity_graph(guestCount):
# create two array for input and outpu of guests with initial value 0
inputA = [0 for x in range(guestCount)]  # [0] * guestCount
outputA = [0 for x in range(guestCount)]
for i in range(guestCount):
for j in range(guestCount):
if a_knows_b(i, j):
# if "a" knows "b" then value for "a" increement by 1 in inputA array
# if "b" knows "a" then value for "a" increment by 1 in outputB array
outputA[i] = outputA[i] + 1
inputA[j] = inputA[j] + 1
try:
# if any index of inputA has value "guestCount - 1" then we will get index of that value
# if at that index in outpuA array value should be "0" to qualify index as celebrity
if inputA.count(guestCount - 1) == 1:
# if (guestCount - 1) is more than 1 then there is no celebrity
celebrity = inputA.index(guestCount - 1)
if not outputA[celebrity]:
return celebrity
else:
return -1
except Exception as e:
return -1

print(find_celebrity_graph(len(MATRIX)))```

## Final Code

Celebrity Problem Code