LeetCode 544: Output Contest Matches

Problem Restatement

We are given n teams labeled from 1 to n.

Team 1 is the strongest team.

Team n is the weakest team.

In each round, we pair the strongest remaining team with the weakest remaining team, the second strongest with the second weakest, and so on.

We need to return the final tournament bracket as a string.

Pairs are written using parentheses and commas:

(a,b)

The input n is always a power of two, so every round can pair all remaining teams evenly. The official constraints say 2 <= n <= 2^12, and n can be written as 2^k.

Input and Output

Function shape:

def findContestMatch(n: int) -> str:
    ...

Examples

For:

n = 2

The teams are:

1, 2

There is only one match:

(1,2)

So the answer is:

"(1,2)"

For:

n = 4

Initial teams:

1, 2, 3, 4

First round pairs strongest with weakest:

(1,4), (2,3)

Second round combines those two matches:

((1,4),(2,3))

So the answer is:

"((1,4),(2,3))"

For:

n = 8

First round:

(1,8), (2,7), (3,6), (4,5)

Second round:

((1,8),(4,5)), ((2,7),(3,6))

Third round:

(((1,8),(4,5)),((2,7),(3,6)))

First Thought: Simulate Each Round

The problem only asks for the bracket structure.

We do not need to know who actually wins each match.

So we can represent each current team or match as a string.

Initially:

["1", "2", "3", "4"]

After one round:

["(1,4)", "(2,3)"]

After another round:

["((1,4),(2,3))"]

When only one string remains, that string is the answer.

Key Insight

At every round, the correct pairing is formed by taking from both ends of the current list:

matches[i]
matches[len(matches) - 1 - i]

The first element is the strongest remaining bracket.

The last element is the weakest remaining bracket.

So each new pair is:

"(" + left + "," + right + ")"

Then the list shrinks by half.

Algorithm

1. Create a list of strings from "1" to str(n).
2. While the list has more than one element:
   1. Create an empty next_round.
   2. Pair matches[0] with matches[-1].
   3. Pair matches[1] with matches[-2].
   4. Continue until the middle.
   5. Replace matches with next_round.
3. Return the only remaining string.

Correctness

Initially, the list contains teams in rank order from strongest to weakest.

During each round, the algorithm pairs the first remaining entry with the last remaining entry, the second with the second last, and so on. This exactly follows the required rule of pairing stronger teams with weaker teams.

Each generated string places the two paired entries inside parentheses separated by a comma, so every match is formatted correctly.

After each round, the winners of these matches are represented by the newly generated match strings. Since the problem asks only for the bracket, not actual winners, this representation is sufficient.

The number of entries is halved every round. Because n is a power of two, the process eventually leaves exactly one string.

That final string represents all rounds of the tournament, so the algorithm returns the required contest match bracket.

Complexity

Let n be the number of teams.

If we count only list operations and ignore string-concatenation cost, there are O(n) pair constructions across all rounds. But the generated strings themselves have total output size proportional to the final bracket representation.

Implementation

class Solution:
    def findContestMatch(self, n: int) -> str:
        matches = [str(i) for i in range(1, n + 1)]

        while len(matches) > 1:
            next_round = []

            left = 0
            right = len(matches) - 1

            while left < right:
                next_round.append(f"({matches[left]},{matches[right]})")
                left += 1
                right -= 1

            matches = next_round

        return matches[0]

Code Explanation

We first create the initial ranked team list:

matches = [str(i) for i in range(1, n + 1)]

For n = 4, this gives:

["1", "2", "3", "4"]

The loop continues until only the final bracket remains:

while len(matches) > 1:

Inside each round, we use two pointers:

left = 0
right = len(matches) - 1

Then we pair the outer entries:

next_round.append(f"({matches[left]},{matches[right]})")

After forming each pair, we move inward:

left += 1
right -= 1

Finally, the current round becomes the next round:

matches = next_round

When the loop ends, the only remaining string is the full bracket.

Recursive Version

The same process can be written recursively.

class Solution:
    def findContestMatch(self, n: int) -> str:
        def build(matches: list[str]) -> str:
            if len(matches) == 1:
                return matches[0]

            next_round = []

            for i in range(len(matches) // 2):
                next_round.append(
                    f"({matches[i]},{matches[len(matches) - 1 - i]})"
                )

            return build(next_round)

        return build([str(i) for i in range(1, n + 1)])

This version expresses the tournament structure directly: build one round, then recursively build the next.

Testing

def run_tests():
    s = Solution()

    assert s.findContestMatch(2) == "(1,2)"
    assert s.findContestMatch(4) == "((1,4),(2,3))"
    assert s.findContestMatch(8) == "(((1,8),(4,5)),((2,7),(3,6)))"
    assert s.findContestMatch(16) == "((((1,16),(8,9)),((4,13),(5,12))),(((2,15),(7,10)),((3,14),(6,11))))"

    print("all tests passed")

run_tests()