277. Find the Celebrity | Plan to write the code later

 Dec. 26, 2021

I had chance to review the algorithm, and I chose to read Leetcode premium solution. 

Optimal solution | O(N) time complexity, O(1) space

• Our code is split into 2 parts.

  The first part finds a celebrity candidate. This requires doing $n - 1$ calls to knows(...) API, and so is $O(n)$.

  The second part is the same as before—checking whether or not a given person is a celebrity. We determined that this is $O(n)$.

  Therefore, we have a total time complexity of $O(n + n) = O(n)$.

public class Solution extends Relation {

    

    private int numberOfPeople;

    

    public int findCelebrity(int n) {

        numberOfPeople = n;

        int celebrityCandidate = 0;

        for (int i = 0; i < n; i++) {

            if (knows(celebrityCandidate, i)) {

                celebrityCandidate = i;

            }

        }

        if (isCelebrity(celebrityCandidate)) {

            return celebrityCandidate;

        }

        return -1;

    }    

    private boolean isCelebrity(int i) {

        for (int j = 0; j < numberOfPeople; j++) {

            if (i == j) continue; // Don't ask if they know themselves.

            if (knows(i, j) || !knows(j, i)) {

                return false;

            }

        }

        return true;

    }

}