LeetCode 544: Output Contest Matches Solution in Python – A Step-by-Step Guide

What Is LeetCode 544: Output Contest Matches?

In LeetCode 544: Output Contest Matches, you’re given an integer n representing the number of teams in a single-elimination tournament (a power of 2), and your task is to return a string representing the matchups of the entire contest. Teams are numbered 1 to n, paired in each round (lowest vs. highest), and the winner of each match advances, with the process repeating until one team remains. For example, with n = 4, the output is "((1,4),(2,3))", showing the first round and final matchup. This problem builds on LeetCode 20: Valid Parentheses for string construction and introduces tournament simulation.

Problem Statement

• Input: n (int)—number of teams (power of 2).
• Output: String—contest matchups in nested format.
• Rules: Pair teams (i vs. n-i+1), winners advance, output as nested pairs.

Constraints

• n is a power of 2 (e.g., 2, 4, 8, 16).
• 1 <= n <= 10³

Examples

• Input: n = 4
• Output: "((1,4),(2,3))"
• Round 1: (1 vs. 4), (2 vs. 3); Final: (winner1 vs. winner2).
• Input: n = 8
• Output: "(((1,8),(4,5)),((2,7),(3,6)))"
• Round 1: (1,8), (4,5), (2,7), (3,6); Round 2: (w1,w2), (w3,w4); Final: (w5,w6).
• Input: n = 2
• Output: "(1,2)"
• Single matchup.

Understanding the Problem: Building the Bracket

To solve LeetCode 544: Output Contest Matches in Python, we need to simulate a single-elimination tournament with n teams (a power of 2), pairing them in each round (lowest vs. highest) and constructing a nested string representation of all matchups. The process mimics a binary tree, where each round halves the number of teams until one remains. A naive approach might manually pair teams round-by-round, but with n up to 10³, we can optimize using recursion or iteration. We’ll explore:

• Best Solution (Recursive Pairing): O(n) time, O(log n) space—elegant and efficient.
• Alternative Solution (Iterative Pairing with Queue): O(n) time, O(n) space—clear but bulkier.

Let’s dive into the recursive solution with a friendly breakdown!

Best Solution: Recursive Pairing

Why Recursive Pairing Wins

The recursive pairing solution is the best for LeetCode 544 because it elegantly constructs the bracket in O(n) time and O(log n) space (recursion stack) by halving the problem at each step, pairing teams naturally, and building the string bottom-up. It’s like organizing a tournament by splitting it into smaller brackets until all matches are set!

How It Works

Think of this as a tournament bracket builder:

• Step 1: Base Case:
• If n = 2, return single matchup "(1,2)".
• Step 2: Recursive Division:
• Split n teams into two halves (n/2 each).
• Recursively get left and right brackets.
• Step 3: Pair Teams:
• Pair 1st half (1 to n/2) with 2nd half (n to n/2+1) in reverse.
• Combine as "(left,right)".
• Step 4: Return String:
• Nested bracket string for all matches.
• Why It Works:
• Recursion mirrors tournament rounds (log n levels).
• Pairing ensures correct matchups (low vs. high).

It’s like a bracket-pairing maestro!

Step-by-Step Example

Example: n = 4

• Step 1: n = 4, split into 2 teams each:
• Left: n = 2, base case → "(1,2)".
• Right: n = 2, base case → "(3,4)".
• Step 2: Combine:
• Pair left (1,2) with right (3,4), adjust numbers:
• Left half: 1, 2 → "(1,4)".
• Right half: 3, 4 → "(2,3)".
• Result: "((1,4),(2,3))".
• Result: "((1,4),(2,3))".

Example: n = 8

• Step 1: n = 8, split into 4 teams each:
• Left: n = 4 → "((1,4),(2,3))".
• Right: n = 4 → "((5,8),(6,7))".
• Step 2: Combine:
• Pair: "((1,8),(4,5)),((2,7),(3,6))".
• Result: "(((1,8),(4,5)),((2,7),(3,6)))".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def findContestMatch(self, n: int) -> str:
        # Step 1: Recursive pairing helper
        def pair_teams(start, size):
            if size == 2:
                # Base case: return single matchup
                return f"({start},{start + size - 1})"

            # Step 2: Recursively split into halves
            half = size // 2
            left = pair_teams(start, half)
            right = pair_teams(start + half, half)

            # Step 3: Combine brackets
            return f"({left},{right})"

        # Step 4: Start with full range
        return pair_teams(1, n)

• Line 4: Helper takes start number and team size.
• Lines 5-7: Base case: 2 teams form "(start,start+1)".
• Lines 10-12: Split into two halves, recurse.
• Line 15: Combine left and right brackets.
• Line 18: Start with 1 to n.
• Time Complexity: O(n)—each team processed once.
• Space Complexity: O(log n)—recursion stack (log n levels).

It’s like a tournament bracket architect!

Alternative Solution: Iterative Pairing with Queue

Why an Alternative Approach?

The iterative pairing with queue solution simulates rounds using a queue, pairing teams and building the string iteratively in O(n) time and O(n) space. It’s more procedural and mimics the tournament step-by-step, making it great for those who prefer iteration over recursion.

How It Works

Picture this as a tournament queue manager:

• Step 1: Initialize queue with teams 1 to n.
• Step 2: Simulate rounds:
• Dequeue pairs, form matchups, enqueue back.
• Step 3: Build string from final round up.
• Step 4: Return bracket string.

It’s like a tournament queue organizer!

Step-by-Step Example

Example: n = 4

• Init: Queue = [1, 2, 3, 4].
• Round 1:
• Pair (1,4) → "(1,4)", (2,3) → "(2,3)".
• Queue = ["(1,4)", "(2,3)"].
• Round 2:
• Pair ("(1,4)", "(2,3)") → "((1,4),(2,3))".
• Result: "((1,4),(2,3))".

Code for Queue Approach

Copy codefrom collections import deque

class Solution:
    def findContestMatch(self, n: int) -> str:
        # Step 1: Initialize queue with teams
        queue = deque(str(i) for i in range(1, n + 1))

        # Step 2: Simulate rounds
        while len(queue) > 1:
            next_round = deque()
            while queue:
                left = queue.popleft()
                right = queue.pop() if queue else None
                if right:
                    next_round.append(f"({left},{right})")
            queue = next_round

        # Step 3: Return final bracket
        return queue[0]

• Line 6: Queue with team numbers as strings.
• Lines 9-15: Pair teams in each round, build matchups.
• Line 18: Return final string.
• Time Complexity: O(n)—each team processed once.
• Space Complexity: O(n)—queue size.

It’s an iterative bracket builder!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n), O(log n), elegant.
• Cons: Recursive stack.
• Iterative (Alternative):
• Pros: O(n), O(n), clear rounds.
• Cons: More space.

Recursive wins for elegance and space!

Additional Examples and Edge Cases

• n = 2: "(1,2)".
• n = 16: Nested 4 levels.
• n = 1: Invalid (assume n ≥ 2).

Recursive handles them all!

Complexity Recap

• Recursive: Time O(n), Space O(log n).
• Iterative: Time O(n), Space O(n).

Recursive’s the space champ!

Key Takeaways

• Recursive: Bracket beauty—learn at Python Basics!
• Iterative: Step-by-step clarity.
• Strings: Tournaments are fun.
• Python: Recursion or queues, your pick!

Final Thoughts: Build That Bracket!

LeetCode 544: Output Contest Matches in Python is a creative tournament challenge. Recursive pairing is your fast track, while iterative queuing offers a clear alternative. Want more? Try LeetCode 20: Valid Parentheses or LeetCode 1022: Sum of Root To Leaf Binary Numbers. Ready to pair? Head to Solve LeetCode 544 on LeetCode and craft that bracket today!