find the celebrity

🏠

Great question, though unfortunately i ran into TLE as i was using a pretty brute-force solution. So, here's the official solution re-written in a more functional way.

1 from functools import lru_cache, reduce
2 
3 class Solution:
4     def findCelebrity(self, n: int) -> int:
5         g = lru_cache(None)(knows)
6         c = reduce(lambda a, b: (a, b)[g(a, b)], range(1, n), 0)
7         return (-1, c)[all(c == j or (g(j, c) and not g(c, j)) for j in range(n))]

Faster than 95% of Python solutions

Now i know what you're thinking: "this is codegolf!" but given it runs faster than 95% of python solutions, and that some Python devs do actually use the functional tools... Ok.. it's codegolf.. but let's take a look anyway.

Caching

1 g = lru_cache(None)(knows)

A decorator is really just a function that takes another function as an argument, so why bother creating yet another wrapper function; might as well use lru_cache to wrap knows directly. This is good for speed.

Candidate Celebrity Hopping

1 c = reduce(lambda a, b: (a, b)[g(a, b)], range(1, n), 0)

This is our candidate search. The main logic is to make b our candidate if they're known, else stick with a. functools.reduce with a ternary handles this logic beautifully.

Celebrity Confirmation

1 return (-1, c)[all(c == j or (g(j, c) and not g(c, j)) for j in range(n))]

Our final step is making sure our candidate is indeed a celebrity. This is easily done with all handling the simple logic of being known to all, but knowing no-one.