Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The two tracked players always survive until they meet; only the winners of other matches are choices. Different choices alter their positions in later rounds. Enumerating possible survivor lists, while memoizing repeated states, finds every attainable meeting round.

Approach

Represent the current players in original-number order. Pair the first with the last, continuing inward. If a pair contains the two tracked players, record this round and stop the branch. Otherwise force tracked players to survive, preserve the middle player's bye when the count is odd, and enumerate one winner from every remaining ordinary match. Deduplicate forced survivors, sort the resulting list, and recurse into the next round. Memoize survivor-list/round states and return the minimum and maximum recorded meeting rounds.

class Solution:
    def earliestAndLatest(self, n: int, f: int, s: int) -> List[int]:
        self.res = set()

        @cache
        def dfs(players, round):
            n = len(players)
            pairs = []

            for i in range(n // 2):
                a = players[i]
                b = players[n - 1 - i]
                if a == f and b == s:
                    self.res.add(round)
                    return
                if not a in (f, s) and not b in (f, s):
                    pairs.append((a, b))

            to_add = (f, s) if n % 2 == 0 else tuple(set([f, s, players[n // 2]]))

            for winners in product(*pairs):
                next = sorted(winners + to_add)
                dfs(tuple(next), round + 1)

        dfs(tuple(x for x in range(1, n + 1)), 1)
        return [min(self.res), max(self.res)]

Complexity analysis

Let S be the number of distinct memoized survivor-list/round states and B the total completed winner combinations generated. With n <= 28 player labels of bounded size, a safe time bound is O(Sn + Bn log(n + 1)): states still require inspection when they terminate without generating a combination. Python uses O(Sn + n) auxiliary space for cached tuples, product choices and active round frames. JavaScript stores O(Sn) state-key characters and can retain O(n^2) winner-prefix entries across its copying chooseWinners recursion, giving O(Sn + n^2) auxiliary space. These are conservative bounds in terms of the explored states and transitions.