Earliest and Latest Rounds Where Players Compete: Tournament Simulation

Tournament brackets have a hidden structure that makes this problem fascinating. You are given n players in a line, and in each round player i fights player n+1-i (1-indexed, counting from the outside in). Losers are eliminated, survivors keep their relative order, and the process repeats. Given two specific players, you need to find the earliest and latest round in which they could possibly meet.

The problem

LeetCode 1900: The Earliest and Latest Rounds Where Players Compete. You have n players in a tournament. In each round, the first player fights the last, the second fights the second-to-last, and so on. If there is an odd number of players, the middle one advances automatically. Winners maintain their relative order and form the lineup for the next round. Given firstPlayer and secondPlayer (1-indexed positions), return an array [earliest, latest] representing the earliest and latest rounds where these two players can compete against each other.

The key insight: recursive state is just three numbers

The brute-force idea of tracking every player's identity through every round is too expensive. Instead, notice that the only things that matter are: the position of firstPlayer, the position of secondPlayer, and the total number of remaining players. You do not need to know who the other players are, only how many sit between and around your two targets.

In each round, the two target players either fight each other (if their positions mirror, meaning left + right == n + 1) or they do not. If they fight, that is the current round. If not, you need to figure out what positions they land in after this round. The key is that the other matches have flexible outcomes. Any non-target player can win or lose, and each combination produces a different arrangement for the next round.

So you enumerate all valid outcomes for the other matches. For each outcome, you compute the new positions of the two target players and the new total count, then recurse. Across all branches, you track the minimum round number (earliest) and maximum round number (latest).

Visual walkthrough

The code

from functools import lru_cache

def earliestAndLatest(n, firstPlayer, secondPlayer):
    @lru_cache(maxsize=None)
    def solve(left, right, total):
        if left + right == total + 1:
            return 1, 1
        if left > right:
            return solve(right, left, total)

        half = total // 2
        nxt = (total + 1) // 2
        mn, mx = total, 0

        for i in range(1, left + 1):
            lo = max(i + 1, right - half + i) if right > half else i + 1
            hi = min(nxt, i + right - left) if right <= half else min(nxt, right - half + i)

            for j in range(lo, hi + 1):
                e, l = solve(i, j, nxt)
                mn = min(mn, e + 1)
                mx = max(mx, l + 1)

        return mn, mx

    return list(solve(firstPlayer, secondPlayer, n))

The function solve(left, right, total) returns a tuple of (earliest round, latest round) where left and right are the 1-indexed positions of the two target players, and total is the number of players remaining.

The base case fires when left + right == total + 1. This means the two target players are mirrors of each other in the current lineup, so they fight this round. Both earliest and latest are 1.

If left > right, we swap them so that left is always the smaller position. This normalization halves the state space and is critical for correct memoization. Without it, solve(3, 1, 6) and solve(1, 3, 6) would be stored as separate entries even though they represent the same situation.

For the recursive case, we enumerate all valid next-round positions (i, j) for the two target players. The variable i ranges from 1 to left because the first target can only end up at a position less than or equal to its current one (players before it might get eliminated, shifting it forward). The bounds for j depend on whether right falls in the first or second half of the lineup. If right is in the second half, its mirror opponent is in the first half, so we need to account for how many survivors come from each side. The lo and hi bounds encode these constraints tightly so we never enumerate an impossible configuration.

Complexity analysis

With n at most 28 (per LeetCode constraints), the total number of states is small enough that memoized recursion runs well within time limits. The enumeration loop at each state is bounded by n/2, keeping the overall work manageable.

The building blocks

1. Recursive simulation with memoization. Instead of simulating every possible tournament bracket, you define a compact state (left, right, total) and cache results. This is the same idea behind game-theory DP problems like Predict the Winner, but applied to a tournament elimination structure.

2. Outside-in pairing logic. The matching rule (player i vs player n+1-i) means you need to reason about positions relative to the midpoint. Understanding which half each target sits in determines the valid ranges for their next-round positions.

3. State normalization. Swapping left and right when left > right ensures each state is visited only once. This is a common trick in symmetric DP problems to cut the search space in half.

Edge cases

• Players are already paired. If firstPlayer + secondPlayer == n + 1 in the initial round, they fight immediately. Answer is [1, 1].
• Adjacent players. When firstPlayer and secondPlayer are next to each other, they still might not be paired if they are not mirrors.
• n = 2. Only two players, so they must fight in Round 1. Answer is always [1, 1].
• Odd number of players. The middle player gets a bye, which changes the next-round count to (n+1)//2 instead of n//2.
• Target players on the same side. If both targets are in the first half (or both in the second half after mirroring), the enumeration bounds differ from the case where they straddle the midpoint.

From understanding to recall

This problem packs a lot of subtlety into a small state space. The pairing rule, the enumeration of valid next-round positions, and the normalization trick all need to come together correctly. Reading through the solution once gives you the general idea, but reproducing it under time pressure is a different skill entirely.

Spaced repetition bridges that gap. You revisit the three-variable state definition, write the enumeration bounds from memory, and after a few reps the pattern becomes automatic. The "recursive tournament simulation" pattern is niche, but the underlying technique of memoized state exploration shows up in many hard DP problems.

The building blocks here (memoized recursion over a compact state, state normalization, and careful bound computation) are transferable to dozens of other problems. Drilling them individually is more effective than solving random hard problems and hoping the patterns stick.

Related posts

• Predict the Winner - Game theory with recursion
• Unique Binary Search Trees - Combinatorial counting
• Climbing Stairs - Building blocks of recursive thinking