A celebrity is a person who is known to all but does not know anyone at a party. If you go to a party of N people, find if there is a celebrity in the party or not.
A square NxN matrix M[][] is used to represent people at the party such that if an element of row i and column j  is set to 1 it means ith person knows jth person. Here M[i][i] will always be 0.
Note: Follow 0 based indexing.
Follow Up: Can you optimize it to O(N)
 
Example 1:
Input:
N = 3
M[][] = {{0 1 0},
         {0 0 0}, 
         {0 1 0}}
Output: 1
Explanation: 0th and 2nd person both
know 1. Therefore, 1 is the celebrity. 
Example 2:
Input:
N = 2
M[][] = {{0 1},
         {1 0}}
Output: -1
Explanation: The two people at the party both
know each other. None of them is a celebrity.
Your Task:
You don't need to read input or print anything. Complete the function celebrity() which takes the matrix M and its size N as input parameters and returns the index of the celebrity. If no such celebrity is present, return -1.
Expected Time Complexity: O(N^2)
Expected Auxiliary Space: O(1)
Constraints:
2 <= N <= 3000
0 <= M[][] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    

    #Function to find if there is a celebrity in the party or not.

    def celebrity(self, M, n):

        # code here 



Solutions:
class Solution:

	def celebrity(self, M, n):
		i = 0
		j = n - 1
		while i < j:
			if M[i][j] == 1:
				i += 1
			else:
				j -= 1
		count = 0
		count2 = 0
		for j in range(n):
			if i != j:
				count += M[j][i]
				count2 += M[i][j]
		if count2 == 0 and count == n - 1:
			return i
		return -1


class Solution:

	def celebrity(self, M, n):
		indegree = {}
		outdegree = {}
		for i in range(n):
			indegree[i] = 0
			outdegree[i] = 0
		for i in range(n):
			for j in range(n):
				if M[i][j] == 0:
					continue
				indegree[j] += 1
				outdegree[i] += 1
		for i in range(n):
			if indegree[i] == n - 1 and outdegree[i] == 0:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		celebrity = []
		normal = []
		for index in range(n):
			normal.append(index) if sum(M[index]) else celebrity.append(index)
		if not celebrity:
			return -1
		not_celeb = []
		for celeb_index in celebrity:
			for index in range(n):
				if index == celeb_index:
					continue
				if not M[index][celeb_index]:
					not_celeb.append(celeb_index)
					break
			if not_celeb and not_celeb[-1] == celeb_index:
				continue
		celeb = [c for c in celebrity if c not in not_celeb]
		return celeb[0] if celeb else -1


from collections import deque

class Solution:

	def celebrity(self, m, n):
		st = deque()
		for i in range(0, n):
			st.append(i)
		while len(st) > 1:
			person1 = st.pop()
			person2 = st.pop()
			if m[person1][person2]:
				st.append(person2)
			else:
				st.append(person1)
		for i in range(0, n):
			if i == st[-1]:
				continue
			if m[st[-1]][i]:
				return -1
			if not m[i][st[-1]]:
				return -1
		return st[-1]


class Solution:

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) >= 2:
			x = stack.pop()
			y = stack.pop()
			if M[x][y] == 1:
				stack.append(y)
			else:
				stack.append(x)
		celeb = stack.pop()
		for i in range(n):
			if i != celeb:
				if M[i][celeb] == 0 or M[celeb][i] == 1:
					return -1
		return celeb


class Solution:

	def celebrity(self, M, n):
		celebrity = False
		for j in range(n):
			if sum([M[x][j] for x in range(n)]) == n - 1:
				if all([M[j][x] == 0 for x in range(n)]):
					return j
		return -1


class Solution:

	def celebrity(self, M, n):
		(one, two) = ([0] * n, [0] * n)
		for i in range(n):
			for j in range(n):
				if M[i][j] == 1:
					one[j] += 1
					two[i] += 1
		for i in range(n):
			if one[i] == n - 1 and two[i] == 0:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		celeb = 0
		for i in range(1, n):
			if M[celeb][i] == 1:
				celeb = i
		for i in range(0, n):
			if i != celeb and (M[celeb][i] == 1 or M[i][celeb] == 0):
				return -1
		return celeb


class Solution:

	def celebrity(self, M, n):
		adj = []
		for i in range(n):
			flag = 0
			for j in range(n):
				if i != j and M[j][i] == 0:
					flag = 1
					break
			if flag == 0:
				g = 0
				for j in range(n):
					if M[i][j] != 0:
						g = 1
						break
				if g == 0:
					return i
		return -1


class Solution:

	def celebrity(self, m, n):
		st = []
		for i in range(n):
			st.append(i)
		while len(st) != 1:
			a = st.pop()
			b = st.pop()
			if m[a][b] == 0:
				st.append(a)
			else:
				st.append(b)
		ans = st[-1]
		row = True
		col = True
		for i in range(n):
			if m[ans][i] == 1:
				row = False
				break
		for j in range(n):
			if j != ans and m[j][ans] == 0:
				col = False
				break
		if row and col:
			return ans
		else:
			return -1


class Solution:

	def celebrity(self, M, n):
		s = []
		for i in range(0, n):
			s.append(i)
		while len(s) > 1:
			a = s[-1]
			s.pop()
			b = s[-1]
			s.pop()
			if M[a][b] == 1:
				s.append(b)
			else:
				s.append(a)
		can = s[-1]
		rowcheck = False
		zerocount = 0
		for i in range(0, n):
			if M[can][i] == 0:
				zerocount += 1
		if zerocount == n:
			rowcheck = True
		colcheck = False
		onecount = 0
		for i in range(0, n):
			if M[i][can] == 1:
				onecount += 1
		if onecount == n - 1:
			colcheck = True
		if colcheck and rowcheck:
			return can
		else:
			return -1


class Solution:

	def celebrity(self, arr, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			a = stack.pop()
			b = stack.pop()
			if arr[a][b] == 1 and arr[b][a] != 1:
				stack.append(b)
			elif arr[a][b] != 1 and arr[b][a] == 1:
				stack.append(a)
		if stack == []:
			return -1
		candidate = stack.pop()
		for elm in arr[candidate]:
			if elm == 1:
				return -1
		for i in range(n):
			if arr[i][candidate] == 0 and i != candidate:
				return -1
		return candidate


class Solution:

	def celebrity(self, M, n):
		arr = []
		for i in range(n):
			flat = 0
			for j in range(n):
				if M[i][j] != 0:
					flat = 1
					break
			if flat != 1:
				arr.append(i)
		for i in arr:
			flat = 0
			for j in range(n):
				if M[j][i] != 1 and i != j:
					flat = 1
					break
			if flat == 0:
				return i
		return -1


def knows(M, f, s):
	return M[f][s]

class Solution:

	def celebrity(self, M, n):
		s = []
		for i in range(n):
			s.append(i)
		while len(s) > 1:
			A = s.pop()
			B = s.pop()
			if knows(M, A, B):
				s.append(B)
			else:
				s.append(A)
		if len(s) == 0:
			return -1
		C = s.pop()
		if knows(M, C, B):
			C = B
		if knows(M, C, A):
			C = A
		for i in range(n):
			if i != C and (knows(M, C, i) or not knows(M, i, C)):
				return -1
		return C


class Solution:

	def knows(self, M, a, b, n):
		if M[a][b] == 1:
			return True
		else:
			return False

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			a = stack[-1]
			stack.pop()
			b = stack[-1]
			stack.pop()
			if self.knows(M, a, b, n):
				stack.append(b)
			else:
				stack.append(a)
		candidate = stack[-1]
		rowCheck = False
		zeroCount = 0
		for i in range(n):
			if M[candidate][i] == 0:
				zeroCount += 1
		if zeroCount == n:
			rowCheck = True
		columnCheck = False
		oneCount = 0
		for i in range(n):
			if M[i][candidate] == 1:
				oneCount += 1
		if oneCount == n - 1:
			columnCheck = True
		if rowCheck == True and columnCheck == True:
			return candidate
		else:
			return -1


class Solution:

	def celebrity(self, M, n):
		a = 0
		b = n - 1
		while a < b:
			if M[a][b] == 1:
				a += 1
			else:
				b -= 1
		for i in range(n):
			if i != a and (M[a][i] == 1 or M[i][a] == 0):
				return -1
		return a


class Solution:

	def celebrity(self, M, n):
		candidate_celeb_idx = -1
		for i in range(n):
			no_of_unk = 0
			for j in range(n):
				if M[i][j] == 0:
					no_of_unk += 1
				if no_of_unk == n:
					candidate_celeb_idx = i
					break
		if candidate_celeb_idx == -1:
			return -1
		no_of_person_know_celeb = 0
		for i in range(n):
			if M[i][candidate_celeb_idx] == 1:
				no_of_person_know_celeb += 1
		if no_of_person_know_celeb == n - 1:
			return candidate_celeb_idx
		else:
			return -1


class Solution:

	def celebrity(self, M, n):
		in_degree = [0 for _ in range(n)]
		out_degree = [0 for _ in range(n)]
		for i in range(n):
			for j in range(n):
				if M[i][j] == 1:
					in_degree[j] += 1
					out_degree[i] += 1
		for i in range(n):
			if in_degree[i] == n - 1 and out_degree[i] == 0:
				return i
		return -1


class Solution:

	def knows(self, mat, n, a, b):
		if mat[a][b] == 1:
			return True
		return False

	def celebrity(self, M, n):
		stk = [i for i in range(n)]
		count = n
		while count > 1:
			a = stk.pop()
			count -= 1
			b = stk.pop()
			count -= 1
			if self.knows(M, n, a, b):
				stk.append(b)
				count += 1
			else:
				stk.append(a)
				count += 1
		candidate = stk.pop()
		flag1 = True
		flag2 = True
		rowCheck = False
		colCheck = False
		for i in range(n):
			if M[candidate][i] == 1:
				flag1 = False
				break
			if M[i][candidate] == 0 and i != candidate:
				flag2 = False
				break
		if flag1 and flag2:
			return candidate
		return -1


class Solution:

	def celebrity(self, M, n):
		st = []
		for i in range(n):
			st.append(i)
		while len(st) > 1:
			a = st.pop()
			b = st.pop()
			if M[a][b]:
				st.append(b)
			else:
				st.append(a)
		celeb = st.pop()
		zero = 0
		for i in range(n):
			if m[celeb][i] == 0:
				zero += 1
		if zero != n:
			return -1
		one = 0
		for i in range(n):
			if M[i][celeb] == 1:
				one += 1
		if one != n - 1:
			return -1
		return celeb


class Solution:

	def celebrity(self, M, n):
		for i in range(n):
			rowSum = sum(M[i])
			colSum = 0
			for j in range(n):
				colSum += M[j][i]
			if rowSum == 0 and colSum == n - 1:
				return i
		return -1


class Solution:

	def celebrity(self, M, N):
		stack = []
		for i in range(N):
			stack.append(i)
		while len(stack) > 1:
			a = stack.pop()
			b = stack.pop()
			if M[a][b] == 1:
				stack.append(b)
			else:
				stack.append(a)
		c = stack.pop()
		for i in range(N):
			if i == c:
				continue
			if M[c][i] or not M[i][c]:
				return -1
		return c


class Solution:

	def celebrity(self, M, N):
		left = 0
		right = N - 1
		while left < right:
			if M[left][right] == 1:
				left += 1
			else:
				right -= 1
		candidate = left
		for i in range(N):
			if i != candidate and (M[candidate][i] == 1 or M[i][candidate] == 0):
				return -1
		return candidate


class Solution:

	def celebrity(self, M, n):
		r = []
		result = 'R'
		for m in M:
			if sum(m) == 0:
				r.append(M.index(m))
		for x in r:
			res = 2
			for m in M:
				if m[x] != 1:
					res -= 1
			if res == 1:
				result = x
		if result != 'R':
			return result
		else:
			return -1


from collections import defaultdict

class Solution:

	def celebrity(self, M, n):
		dictt = defaultdict(int)
		graph = M
		for i in range(len(graph)):
			for j in range(len(graph[i])):
				if i != j and graph[i][j] == 1:
					dictt[i] -= 1
					dictt[j] += 1
		for (key, value) in dictt.items():
			if value == n - 1:
				return key
		return -1


class Solution:

	def celebrity(self, M, n):
		In = [0] * n
		out = [0] * n
		for i in range(n):
			for j in range(n):
				if M[i][j] == 1:
					In[j] += 1
					out[i] += 1
		for i in range(n):
			if In[i] == n - 1 and out[i] == 0:
				return i
		return -1


def knows(M, a, b, n):
	if M[a][b] == 1:
		return True
	else:
		return False

class Solution:

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) != 1:
			a = stack.pop()
			b = stack.pop()
			if knows(M, a, b, n):
				stack.append(b)
			else:
				stack.append(a)
		celeb = stack[-1]
		rowcheck = False
		zero = 0
		for i in range(n):
			if M[celeb][i] == 0:
				zero += 1
		if zero == n:
			rowcheck = True
		colcheck = False
		ones = 0
		for i in range(n):
			if M[i][celeb] == 1:
				ones += 1
		if ones == n - 1:
			colcheck = True
		if rowcheck and colcheck:
			return celeb
		return -1


class Solution:

	def celebrity(self, M, n):
		stk = [i for i in range(n)]
		while len(stk) != 1:
			a = stk.pop()
			b = stk.pop()
			if M[a][b] == 1:
				stk.append(b)
			elif M[b][a] == 1:
				stk.append(a)
			if len(stk) == 0:
				return -1
		candidate = stk.pop()
		for i in range(n):
			if i != candidate and M[candidate][i] == 1:
				return -1
			if i != candidate and M[i][candidate] == 0:
				return -1
		return candidate


class Solution:

	def celebrity(self, M, n):
		first = 0
		last = n - 1
		while first < last:
			if M[first][last] == 1:
				first += 1
			else:
				last -= 1
		for i in range(n):
			if i != first and (M[first][i] == 1 or M[i][first] == 0):
				return -1
		return first


class Solution:

	def celebrity(self, M, n):
		row_len = n
		col_len = n
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			a = stack[-1]
			stack.pop()
			b = stack[-1]
			stack.pop()
			x = self.helper(a, b, M)
			if x:
				stack.append(b)
			else:
				stack.append(a)
		celebrity = stack.pop()
		for i in range(n):
			if M[celebrity][i] == 1:
				return -1
		count = 0
		for i in range(n):
			if M[i][celebrity] == 1:
				count += 1
		if count == n - 1:
			return celebrity
		return -1

	def helper(self, a, b, arr):
		if arr[a][b] == 1:
			return True
		return False


class Solution:

	def celebrity(self, mat, n):
		st = []
		for i in range(n):
			st.append(i)
		while len(st) > 1:
			a = st.pop()
			b = st.pop()
			if mat[a][b] == 1 and mat[b][a] != 1:
				st.append(b)
			elif mat[a][b] != 1 and mat[b][a] == 1:
				st.append(a)
		if not st:
			return -1
		x = st[-1]
		for i in range(n):
			if x != i:
				if mat[x][i] != 0 or mat[i][x] != 1:
					return -1
		return st[-1]


class Solution:

	def knows(self, a, b, M):
		if M[a][b] == 1:
			return True
		return False

	def celebrity(self, M, n):
		stack = []
		res = -1
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			a = stack.pop()
			b = stack.pop()
			if self.knows(a, b, M):
				stack.append(b)
			else:
				stack.append(a)
		celeb = stack[-1]
		count = 0
		count2 = 0
		for i in range(n):
			if M[celeb][i] == 0:
				count += 1
		if count != n:
			return -1
		for i in range(n):
			if M[i][celeb] == 1:
				count2 += 1
		if count2 != n - 1:
			return -1
		return celeb


class Solution:

	def celebrity(self, mat, n):
		for i in range(n):
			if i == 0:
				b = mat[0][1]
				a = mat[1][0]
			else:
				a = mat[0][i]
				b = mat[i][0]
			if a != 1 or b != 0:
				continue
			f1 = 0
			for j in range(1, n):
				if j != i:
					if b != mat[i][j]:
						f1 = 1
						break
			if f1 != 0:
				continue
			f2 = 0
			for j in range(1, n):
				if j != i:
					if a != mat[j][i]:
						f2 = 1
						break
			if not f1 and (not f2):
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		flag = False
		for i in range(n):
			if sum(M[i]) == 0:
				for j in range(n):
					if M[j][i] != 1 and i != j:
						flag = False
						break
					else:
						flag = True
			if flag == True:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		ith_index = []
		jth_index = []
		for i in range(n):
			sum_i = 0
			for j in range(n):
				sum_i += M[i][j]
			if sum_i == 0:
				ith_index.append(i)
		if len(ith_index) != 1:
			return -1
		else:
			for j in range(n):
				sum_j = 0
				for i in range(n):
					sum_j += M[i][j]
				if sum_j == n - 1:
					return ith_index[0]
			return -1


class Solution:

	def celebrity(self, M, n):
		s = [[] for i in range(n)]
		for i in range(n):
			for j in range(n):
				if M[i][j] == 1:
					s[i].append(j)
		for i in range(n):
			if not s[i]:
				flag = True
				for j in range(n):
					if i != j and i not in s[j]:
						flag = False
						break
				if flag:
					return i
		return -1


class Solution:

	def celebrity(self, M, n):
		i = 0
		j = n - 1
		candidate = -1
		while i < j:
			if M[j][i] == 1:
				j -= 1
			else:
				i += 1
		candidate = i
		for i in range(n):
			if candidate != i:
				if M[candidate][i] == 1 or M[i][candidate] == 0:
					return -1
		return candidate


class Solution:

	def celebrity(self, M, n):

		def check(M, x, y):
			if M[x][y] == 1 or M[y][x] == 0:
				return False
			return True
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			a = stack.pop()
			b = stack.pop()
			if check(M, a, b):
				stack.append(a)
			if check(M, b, a):
				stack.append(b)
		if len(stack) == 0:
			return -1
		val = stack[0]
		for i in range(n):
			if i == val:
				continue
			if M[i][val] != 1 or M[val][i] != 0:
				return -1
		return val


class Solution:

	def celebrity(self, M, n):
		stack = []
		size = n
		for i in range(n):
			stack.append(i)
		while size > 1:
			s1 = stack.pop()
			s2 = stack.pop()
			if M[s1][s2] == 1:
				stack.append(s2)
			else:
				stack.append(s1)
			size -= 1
		for i in range(n):
			if i != stack[0] and M[i][stack[0]] == 0:
				return -1
		if M[stack[0]].count(0) != n:
			return -1
		return stack[0]


class Solution:

	def celebrity(self, M, n):
		cel = 0
		for i in range(n):
			c = 0
			for j in range(n):
				if M[i][j] == 0:
					c += 1
			if c == n:
				cel = i
				break
		for i in range(n):
			if i == cel:
				continue
			if M[i][cel] != 1:
				cel = -1
				break
		return cel


class Solution:

	def celebrity(self, M, n):
		c = 0
		index = -1
		stack = []
		for i in range(n):
			cnt = 0
			for j in range(n):
				if M[j][i] == 1:
					cnt += 1
			if cnt == n - 1:
				stack.append(i)
		for i in stack:
			if M[i].count(0) == n:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		ans = -1
		stk = [i for i in range(n)]
		while len(stk) > 1:
			i = stk.pop()
			j = stk.pop()
			if M[i][j] == 1 and M[j][i] == 0:
				stk.append(j)
			elif M[i][j] == 0 and M[j][i] == 1:
				stk.append(i)
			else:
				continue
		if len(stk) == 0:
			return -1
		else:
			ind = stk[-1]
			for i in range(n):
				if i == ind:
					continue
				if M[i][ind] == M[ind][i]:
					return -1
			return ind


class Solution:

	def celebrity(self, graph, n):
		(ind, outd) = ([0] * n, [0] * n)
		for i in range(n):
			for j in range(n):
				if graph[i][j] == 1:
					ind[j] += 1
					outd[i] += 1
		for i in range(n):
			if ind[i] == n - 1 and outd[i] == 0:
				return i
		return -1


class Solution:

	def celebrity(self, matrix, n):
		celebrity_index = 0
		for i in range(1, n):
			if matrix[celebrity_index][i] == 1:
				celebrity_index = i
		for i in range(n):
			if celebrity_index != i:
				if matrix[celebrity_index][i] == 1 or matrix[i][celebrity_index] == 0:
					return -1
		return celebrity_index


class Solution:

	def celebrity(self, matrix, n):
		for i in range(n):
			ind_celebrity = i
			for j in range(n):
				if matrix[i][j] != 0:
					ind_celebrity = -1
					break
			if ind_celebrity != -1:
				for j in range(n):
					if i != j and matrix[j][i] != 1:
						ind_celebrity = -1
						break
			if ind_celebrity != -1:
				return ind_celebrity
		return -1


class Solution:

	def celebrity(self, M, n):
		N = n
		stk = [i for i in range(N)]
		while len(stk) > 1:
			a = stk.pop()
			b = stk.pop()
			if M[a][b]:
				stk.append(b)
			else:
				stk.append(a)
		celeb = stk[0]
		cknows = 0
		cnot = 0
		for i in range(N):
			if M[i][celeb]:
				cknows += 1
			if M[celeb][i]:
				cnot += 1
		if cknows == N - 1 and cnot == 0:
			return celeb
		else:
			return -1


class Solution:

	def celebrity(self, M, n):
		st = [i for i in range(n)]
		while len(st) != 0:
			x = st.pop()
			if len(st) != 0:
				y = st.pop()
			else:
				break
			if M[x][y] == 1:
				st.append(y)
			else:
				st.append(x)
		for i in range(n):
			if i != x and M[i][x] == 0:
				return -1
		for i in range(n):
			if M[x][i] == 1:
				return -1
		return x


class Solution:

	def celebrity(self, M, n):
		for row in range(n):
			maybeCeleb = True
			for col in range(n):
				if M[row][col] != 0:
					maybeCeleb = False
			if maybeCeleb:
				for r in range(n):
					if r != row:
						if M[r][row] != 1:
							maybeCeleb = False
							break
			if maybeCeleb:
				return row
		return -1


class Solution:

	def celebrity(self, M, n):
		left = 0
		right = n - 1
		while left < right:
			if M[left][right]:
				left += 1
			else:
				right -= 1
		potential_celebrity = left
		count = 0
		for index in range(n):
			if index == potential_celebrity:
				continue
			if M[potential_celebrity][index] == 1:
				return -1
			if M[index][potential_celebrity] == 1:
				count += 1
		if count < n - 1:
			return -1
		return potential_celebrity


class Solution:

	def celebrity(self, M, n):
		st = []
		for i in range(n):
			st.append(i)
		while len(st) >= 2:
			a = st.pop()
			b = st.pop()
			if M[a][b] == 1:
				st.append(b)
			else:
				st.append(a)
		pot = st.pop()
		for i in range(n):
			if i != pot:
				if M[pot][i] == 1 or M[i][pot] == 0:
					return -1
		return pot


class Solution:

	def celebrity(self, M, n):
		for i1 in range(n):
			celeb = True
			for i2 in range(n):
				if M[i1][i2] == 1:
					celeb = False
					break
			if celeb:
				for i2 in range(n):
					if M[i2][i1] == 0:
						if i1 != i2:
							return -1
				return i1
		return -1


class Solution:

	def known_by_all(self, M, i):
		kba = 1
		for j in range(n):
			if j != i and M[j][i] != 1:
				kba = 0
				break
		return kba

	def celebrity(self, M, n):
		nobody = [[0] * n for __ in range(n)]
		if nobody == M:
			return -1
		for i in range(n):
			if sum(M[i]) == 0 and self.known_by_all(M, i):
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		candi = []
		ans = []
		for i in range(n):
			if M[i] == [0] * n:
				candi.append(i)
		for i in candi:
			for j in range(n):
				if j == i:
					continue
				elif M[j][i] == 0:
					break
			else:
				ans.append(i)
		if len(ans) == 0:
			return -1
		else:
			return ans[0]


class Solution:

	def celebrity(self, M, n):
		knows_me = [0] * n
		i_know = [0] * n
		for i in range(n):
			for j in range(n):
				if M[i][j] == 1:
					i_know[i] += 1
					knows_me[j] += 1
		for i in range(n):
			if i_know[i] == 0 and knows_me[i] == n - 1:
				return i
		return -1


from collections import deque

def knows(a, b, M):
	return M[a][b]

class Solution:

	def celebrity(self, M, n):
		s = deque()
		for i in range(n):
			s.append(i)
		while len(s) > 1:
			a = s.pop()
			b = s.pop()
			if knows(a, b, M):
				s.append(b)
			else:
				s.append(a)
		c = s.pop()
		for i in range(n):
			if i != c and (knows(c, i, M) or not knows(i, c, M)):
				return -1
		return c


class Solution:

	def celebrity(self, M, n):
		potential_celebrity = 0
		for i in range(1, n):
			if M[potential_celebrity][i]:
				potential_celebrity = i
		for i in range(n):
			if i == potential_celebrity:
				continue
			if M[potential_celebrity][i] or not M[i][potential_celebrity]:
				return -1
		return potential_celebrity


class Solution:

	def celebrity(self, M, n):
		inDegree = [0 for _ in range(n)]
		outDegree = [sum(M[i]) for i in range(n)]
		for i in range(n):
			for j in range(n):
				inDegree[i] += M[j][i]
		for i in range(n):
			if inDegree[i] == n - 1 and outDegree[i] == 0:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		i = 0
		while i < n:
			j = 0
			while j < n:
				if j == i and M[i][i] == 0:
					j += 1
					continue
				if M[i][j] == 0 and M[j][i] == 1:
					j += 1
				else:
					break
			if j == n:
				return i
			i += 1
		return -1


class Solution:

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			i = stack.pop()
			j = stack.pop()
			if M[i][j] == 1:
				stack.append(j)
			else:
				stack.append(i)
		for j in range(n):
			if M[stack[-1]][j] != 0:
				return -1
		for i in range(n):
			if i != stack[-1] and M[i][stack[-1]] != 1:
				return -1
		return stack[-1]


class Solution:

	def celebrity(self, M, n):
		stack = list(range(n))
		while len(stack) > 1:
			i = stack.pop()
			j = stack.pop()
			if M[i][j]:
				stack.append(j)
			else:
				stack.append(i)
		if not stack:
			return -1
		celebrity = stack.pop()
		for i in range(n):
			if i != celebrity and (M[celebrity][i] or not M[i][celebrity]):
				return -1
		return celebrity


class Solution:

	def celebrity(self, matrix, n):
		d = {}
		for i in range(n):
			d[i] = []
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 1:
					d[i].append(j)
		sum = {}
		for i in range(n):
			sum[i] = 0
		for i in d:
			for j in d[i]:
				sum[j] = sum[j] + 1
		ans = -1
		for i in sum:
			if sum[i] == n - 1 and d[i] == []:
				ans = i
		return ans


from collections import defaultdict

class Solution:

	def celebrity(self, M, n):
		i = 0
		j = n - 1
		ans = -1
		while i < j:
			if M[i][j]:
				i += 1
			else:
				j -= 1
		pot = i
		for i in range(n):
			if i != pot:
				if M[i][pot] == 0 or M[pot][i] == 1:
					return -1
		return pot


class Solution:

	def celebrity(self, M, n):

		def everyoneKnows(i):
			for j in range(len(M)):
				if i != j and (M[j][i] == 0 or M[i][j] == 1):
					return False
			return True
		st = [i for i in range(len(M))]
		while len(st) > 1:
			a = st.pop()
			b = st.pop()
			if M[a][b]:
				st.append(b)
			else:
				st.append(a)
		last = st.pop()
		if everyoneKnows(last):
			return last
		else:
			return -1


class Solution:

	def celebrity(self, M, n):

		def knowsNoOne(arr):
			for p in arr:
				if p == 1:
					return False
			return True

		def everyoneKnows(i):
			for j in range(len(M)):
				if i != j and M[j][i] == 0:
					return False
			return True
		for i in range(len(M)):
			if knowsNoOne(M[i]):
				if everyoneKnows(i):
					return i
		return -1


class Solution:

	def celebrity(self, M, n):
		inDegree = [0 for x in range(0, n)]
		outDegree = [0 for x in range(0, n)]
		for i in range(0, len(M)):
			for j in range(0, len(M[i])):
				if M[i][j] == 1:
					a = i
					b = j
					inDegree[b] += 1
					outDegree[a] += 1
		for i in range(0, n):
			if inDegree[i] == n - 1 and outDegree[i] == 0:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		s = []
		for i in range(n):
			s.append(i)
		while len(s) > 1:
			A = s.pop()
			B = s.pop()
			if M[A][B] == 1:
				s.append(B)
			else:
				s.append(A)
		elem = s.pop()
		for i in range(0, n):
			if i != elem:
				if M[i][elem] == 0 or M[elem][i] == 1:
					return -1
		return elem


import collections

class Solution:

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) >= 2:
			cand1 = stack.pop(-1)
			cand2 = stack.pop(-1)
			if M[cand2][cand1] == 0:
				stack.append(cand2)
			elif M[cand1][cand2] == 0:
				stack.append(cand1)
		if len(stack) == 0:
			return -1
		poss = stack[0]
		for i in range(n):
			if i != poss:
				if M[poss][i] == 1:
					return -1
				if M[i][poss] == 0:
					return -1
		return poss


import collections

class Solution:

	def celebrity(self, M, n):
		adj = collections.defaultdict(list)
		indegree = [0] * n
		outdegree = [0] * n
		for i in range(n):
			for j in range(n):
				if M[i][j] == 1:
					indegree[j] += 1
					outdegree[i] += 1
		for i in range(n):
			if indegree[i] == n - 1 and outdegree[i] == 0:
				return i
		return -1


class Solution:

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) > 1:
			p1 = stack.pop()
			p2 = stack.pop()
			if M[p1][p2]:
				stack.append(p2)
			else:
				stack.append(p1)
		potential_celebrity = stack.pop()
		for i in range(n):
			if i != potential_celebrity:
				if M[potential_celebrity][i] or not M[i][potential_celebrity]:
					return -1
		return potential_celebrity


class Solution:

	def celebrity(self, M, n):
		ans = -1
		f = 0
		d = {}
		for i in range(len(M)):
			for j in range(len(M[0])):
				if M[i][j] == 1:
					if j not in d:
						d[j] = 1
					else:
						d[j] += 1
		for i in d.keys():
			if d[i] == n - 1:
				if M[i].count(1) == 0:
					ans = i
		return ans
		return -1


class Solution:

	def celebrity(self, M, n):
		stack = []
		for i in range(n):
			stack.append(i)
		while len(stack) >= 2:
			i = stack.pop()
			j = stack.pop()
			if M[i][j] == 0:
				stack.append(i)
			else:
				stack.append(j)
		pot = stack[-1]
		for i in range(n):
			if i != pot:
				if M[i][pot] == 0 or M[pot][i] == 1:
					return -1
		return pot


class Solution:

	def celebrity(self, M, n):
		(i, j) = (0, n - 1)
		while i < j:
			if M[i][j]:
				i += 1
			else:
				j -= 1
		for z in range(n):
			if i != z:
				if M[i][z] == 0 and M[z][i] == 1:
					continue
				else:
					return -1
		else:
			return i


class Solution:

	def celebrity(self, M, n):
		index = -1
		introvert = 0
		poss_intro = []
		x = []
		for i in range(n):
			M[i][i] = 1
			if M[0][i] == 1:
				poss_intro.append(i)
		for i in range(len(poss_intro) - 1, -1, -1):
			for j in range(n):
				if M[j][poss_intro[i]] == 1:
					continue
				else:
					x.append(i)
					break
		if len(x) + 1 == len(poss_intro):
			for i in x:
				poss_intro.pop(i)
			index = poss_intro[0]
			for i in range(n):
				if i != index:
					if M[index][i] == 1:
						return -1
			else:
				return int(poss_intro[0])
		else:
			return -1


class Solution:

	def celebrity(self, M, n):
		index = -1
		introvert = 0
		for i in range(n):
			if M[i].count(0) == n:
				index = i
				introvert += 1
			if introvert > 1:
				return -1
		if introvert == 0:
			return -1
		M[index][index] = 1
		for i in range(n):
			if M[i][index] == 1:
				continue
			else:
				return -1
		else:
			return index