LeetCode 544 - Output Contest Matches

The problem asks us to simulate the structure of a playoff tournament bracket. We are given n teams, numbered from 1 to n, where smaller numbers represent stronger teams.

leetcodemediumstringrecursionsimulation

LeetCode Problem 544

Difficulty: 🟡 Medium
Topics: String, Recursion, Simulation

Solution

Problem Understanding

The problem asks us to simulate the structure of a playoff tournament bracket. We are given n teams, numbered from 1 to n, where smaller numbers represent stronger teams. The tournament pairing rule is fixed: in every round, the strongest remaining team must play against the weakest remaining team.

The output is not the winner of the tournament. Instead, we must return a string representation of the entire contest structure. Each match is represented using parentheses and commas. For example, if team 1 plays team 8, that match is represented as (1,8).

After each round, the winners advance conceptually, but we do not need to determine actual winners. We only need to preserve the tournament structure. This means that previous match strings become participants in the next round.

For example, when n = 4:

  • First round:

  • (1,4)

  • (2,3)

  • Second round:

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

The final output is the complete nested representation.

The constraints state that:

  • n == 2^x
  • 1 <= x <= 12

This means:

  • n is always a power of two.
  • The maximum value of n is 4096.

Because the number of teams is relatively small, we do not need highly advanced optimizations. A direct simulation is efficient enough.

An important guarantee is that the tournament always has an even number of participants in every round. Since n is a power of two, pairing can continue cleanly until only one final match remains.

Several edge cases are important:

  • The smallest possible input is n = 2, where the answer is simply (1,2).
  • Large values such as n = 4096 create deeply nested strings, so string construction should be handled carefully.
  • Incorrect pairing order is a common bug. We must always pair the leftmost remaining team with the rightmost remaining team in each round.

Approaches

Brute Force Approach

A brute force strategy would attempt to explicitly simulate every round using recursive tree construction and repeated string concatenation. One possible implementation is to build an actual binary tournament tree where each node stores its left and right children and then perform a traversal to generate the final string.

This works because every round combines pairs of teams into larger match structures until a single root node remains.

However, constructing a full tree structure introduces unnecessary overhead. We do not actually need a separate tree representation because the required output already naturally forms the structure we need.

Repeated recursive traversal and extra object allocation make the solution more complicated than necessary.

Optimal Approach

The key observation is that the tournament structure can be built iteratively using strings alone.

Initially, every team is represented as its own string:

["1", "2", "3", ..., "n"]

In each round:

  • Pair the first and last entries.
  • Pair the second and second-last entries.
  • Continue inward.
  • Replace each pair with a new combined string:
"(" + left + "," + right + ")"

After one round, the number of entries is cut in half.

This process continues until only one string remains.

The reason this works is that every round preserves the exact tournament structure required by the problem statement. The resulting nested string directly represents the playoff bracket.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n log n) Builds explicit recursive tournament structures
Optimal O(n log n) O(n) Iteratively combines match strings round by round

Algorithm Walkthrough

  1. Create an array of strings representing all teams.

For example, if n = 8:

["1", "2", "3", "4", "5", "6", "7", "8"]

We use strings because the final result is a nested string expression. 2. While more than one team remains, process one tournament round.

Each round reduces the number of entries by half. 3. Use two pointers, one at the beginning and one at the end.

The left pointer represents the strongest remaining team.

The right pointer represents the weakest remaining team. 4. Pair the teams.

Construct a new string:

"(" + leftTeam + "," + rightTeam + ")"

For example:

"(1,8)"
  1. Store all newly formed match strings in a new array.

After processing all pairs, replace the old array with the new one. 6. Repeat until only one string remains.

That final string is the complete tournament bracket.

Why it works

The algorithm maintains an invariant: after every round, the array contains the correctly formatted match structures for all surviving tournament branches.

Because each round always pairs the strongest remaining entry with the weakest remaining entry, the algorithm exactly matches the required playoff rules. Repeatedly reducing the array guarantees that the final remaining string represents the complete tournament structure.

Python Solution

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

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

            left = 0
            right = len(teams) - 1

            while left < right:
                match = f"({teams[left]},{teams[right]})"
                next_round.append(match)

                left += 1
                right -= 1

            teams = next_round

        return teams[0]

The implementation starts by converting all team numbers into strings. This simplifies later concatenation because every round produces larger string expressions.

The outer while loop simulates tournament rounds. As long as more than one participant remains, another round must be played.

Inside each round, two pointers are used:

  • left starts at the beginning of the array.
  • right starts at the end.

These pointers ensure we always pair the strongest remaining team with the weakest remaining team.

For every pair, we create a formatted match string and append it to next_round.

After processing all pairs, teams is replaced with next_round, reducing the participant count by half.

Eventually, only one fully nested match string remains, which is returned as the answer.

Go Solution

import "strconv"

func findContestMatch(n int) string {
    teams := make([]string, n)

    for i := 0; i < n; i++ {
        teams[i] = strconv.Itoa(i + 1)
    }

    for len(teams) > 1 {
        nextRound := []string{}

        left := 0
        right := len(teams) - 1

        for left < right {
            match := "(" + teams[left] + "," + teams[right] + ")"
            nextRound = append(nextRound, match)

            left++
            right--
        }

        teams = nextRound
    }

    return teams[0]
}

The Go implementation follows the same logic as the Python version.

One notable difference is that integers must be explicitly converted to strings using strconv.Itoa.

Slices are used to store the current round's participants and the next round's generated matches. Since Go strings are immutable, concatenation creates new strings similarly to Python.

No integer overflow concerns exist because the constraints are small.

Worked Examples

Example 1

Input:

n = 4

Initial teams:

Index Value
0 "1"
1 "2"
2 "3"
3 "4"

First round pairings:

Left Right Match
"1" "4" "(1,4)"
"2" "3" "(2,3)"

New array:

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

Second round:

Left Right Match
"(1,4)" "(2,3)" "((1,4),(2,3))"

Final array:

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

Output:

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

Example 2

Input:

n = 8

Initial array:

["1", "2", "3", "4", "5", "6", "7", "8"]

First round:

Pair Result
1 vs 8 "(1,8)"
2 vs 7 "(2,7)"
3 vs 6 "(3,6)"
4 vs 5 "(4,5)"

Array after round 1:

["(1,8)", "(2,7)", "(3,6)", "(4,5)"]

Second round:

Pair Result
"(1,8)" vs "(4,5)" "((1,8),(4,5))"
"(2,7)" vs "(3,6)" "((2,7),(3,6))"

Array after round 2:

["((1,8),(4,5))", "((2,7),(3,6))"]

Third round:

Pair Result
"((1,8),(4,5))" vs "((2,7),(3,6))" "(((1,8),(4,5)),((2,7),(3,6)))"

Final output:

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

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) There are log n rounds, and each round processes O(n) total string content
Space O(n) The algorithm stores the current tournament layer

The tournament contains log n rounds because the number of participants is halved each time.

Across all rounds, every team participates once per level of nesting. Since string sizes grow over time, the total work across all concatenations becomes O(n log n).

The space usage is O(n) because we only store the current round and next round arrays, not the entire tournament tree separately.

Test Cases

solution = Solution()

# Smallest valid input
assert solution.findContestMatch(2) == "(1,2)"

# Example case with one additional round
assert solution.findContestMatch(4) == "((1,4),(2,3))"

# Example case with three rounds
assert solution.findContestMatch(8) == "(((1,8),(4,5)),((2,7),(3,6)))"

# Larger power of two
assert solution.findContestMatch(16) == (
    "((((1,16),(8,9)),((4,13),(5,12))),"
    "(((2,15),(7,10)),((3,14),(6,11))))"
)

# Verify structure remains balanced
result = solution.findContestMatch(32)
assert result.count("(") == result.count(")")

# Verify all team numbers appear
result = solution.findContestMatch(8)
for i in range(1, 9):
    assert str(i) in result

# Stress test near upper constraint
result = solution.findContestMatch(4096)
assert isinstance(result, str)
assert len(result) > 0
Test Why
n = 2 Validates smallest possible tournament
n = 4 Verifies basic recursive nesting
n = 8 Tests multiple tournament rounds
n = 16 Confirms larger bracket construction
Parentheses balance check Ensures formatting correctness
Team inclusion check Verifies no teams are lost
n = 4096 Stress tests upper constraint

Edge Cases

Smallest Input Size

The smallest valid input is n = 2. In this case, there is only one match and no recursive nesting beyond a single pair.

A buggy implementation might incorrectly enter another round or mishandle indexing. This solution handles it naturally because the first round immediately reduces the array to one element.

Deeply Nested Tournament Strings

For large values such as n = 4096, the resulting string becomes very deeply nested and quite large.

An inefficient recursive implementation with excessive copying or tree traversal could become unnecessarily slow or memory-heavy. The iterative approach avoids recursion depth concerns and constructs the bracket layer by layer.

Incorrect Pairing Order

One of the easiest mistakes is pairing adjacent teams instead of strongest versus weakest.

For example, incorrectly generating:

(1,2),(3,4)

instead of:

(1,4),(2,3)

would violate the tournament rules.

Using two pointers guarantees that the leftmost and rightmost remaining participants are always paired correctly in every round.