277. Find the Celebrity - cocoder39/coco39_LC GitHub Wiki

277. Find the Celebrity

notes 2023

class Solution:
    def findCelebrity(self, n: int) -> int:
        candidate = 0
        for i in range(1, n):
            if knows(candidate, i): 
                candidate = i
        # [0, candidate-1] is not Celebrity because they knows someone
        # [candidate+1, n-1] is not Celebrity because candidate doesn't know them
        if self.isCelebrity(candidate, n):
            return candidate
        return -1

    def isCelebrity(self, candidate, n):
        for i in range(n):
            if i == candidate:
                continue
            if not knows(i, candidate) or knows(candidate, i):
                return False
        return True

===============================================================

Notes 2020:

class Solution:
    def findCelebrity(self, n: int) -> int:
        cur_candidate, next_candidate = 0, 1
        while next_candidate < n:
            if knows(cur_candidate, next_candidate):
                cur_candidate = next_candidate
            next_candidate = next_candidate + 1
                
        for i in range(n):
            if i == cur_candidate:
                continue
            if not knows(i, cur_candidate) or knows(cur_candidate, i):
                return -1
        return cur_candidate

========================================================================

the candidate move forward only if we found candidate knows sb or sb doesn't know candidate

int findCelebrity(int n) {
        int res = 0;
        for (int i = 1; i < n; i++) {
            //if (knows(res, i))  res = i;
            if (! knows(i, res))    res = i;
        }
        
        for (int i = 0; i < n; i++) {
            if (i == res)   continue;
            if (! knows(i, res) || knows(res, i))   return -1;
        }
        return res;
    }