# 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:

```text
(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

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | The final contest match string |
| Team labels | Integers from `1` to `n` |
| Pairing rule | Strongest remaining with weakest remaining |
| Guarantee | `n` is a power of two |

Function shape:

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

## Examples

For:

```python
n = 2
```

The teams are:

```text
1, 2
```

There is only one match:

```text
(1,2)
```

So the answer is:

```python
"(1,2)"
```

For:

```python
n = 4
```

Initial teams:

```text
1, 2, 3, 4
```

First round pairs strongest with weakest:

```text
(1,4), (2,3)
```

Second round combines those two matches:

```text
((1,4),(2,3))
```

So the answer is:

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

For:

```python
n = 8
```

First round:

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

Second round:

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

Third round:

```text
(((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:

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

After one round:

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

After another round:

```python
["((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:

```python
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:

```python
"(" + 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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` characters written | The output string grows across `log n` rounds |
| Space | `O(n log n)` output size | The final bracket string contains all team labels and parentheses |

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

```python
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:

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

For `n = 4`, this gives:

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

The loop continues until only the final bracket remains:

```python
while len(matches) > 1:
```

Inside each round, we use two pointers:

```python
left = 0
right = len(matches) - 1
```

Then we pair the outer entries:

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

After forming each pair, we move inward:

```python
left += 1
right -= 1
```

Finally, the current round becomes the next round:

```python
matches = next_round
```

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

## Recursive Version

The same process can be written recursively.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `n = 2` | Smallest tournament |
| `n = 4` | One intermediate round |
| `n = 8` | Checks nested pairing order |
| `n = 16` | Checks deeper recursive structure |