Problem statement

https://leetcode.com/problems/find-the-celebrity/

Solution

Let us keep cand: possible candidate for celebrity. Let us consider persons one by one. If knows(cand, i) is true, it means that cand can not be celebrity any more, so we need to change it. If it is false, it means that i can not be celebrity, becaouse everone knows celebrity, so in any case we have only one candidate rest. In the end we need to check that cand is indeed celebrity, what we did so far is just make sure that others can not be celebrities. So, we check all 2n - 2 connections.

Complexity

Time complexity is $O(n)$, in the worst case it can be $3n$. Space complexity is $O(1)$.

Code

class Solution:
    def findCelebrity(self, n):
        cand = 0
        for i in range(1, n):
            if knows(cand, i): cand = i
            
        for i in range(n):
            if i == cand: continue
            if not knows(i, cand) or knows(cand, i): return -1
            
        return cand