Output Contest Matches — LeetCode 544 Python Solution

The problem

During the NBA playoffs, we always set the rather strong team to play with the rather weak team, like making the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Given n teams, return their final contest matches in the form of a string.

Example

Input

n = 4

Output

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

Explanation

In the first round, we pair the team 1 and 4, the teams 2 and 3 together, as we need to make the strong team and weak team together.

Python solution

class Solution:
    def findContestMatch(self, n: int) -> str:
        s = [str(i + 1) for i in range(n)]
        while n > 1:
            for i in range(n >> 1):
                s[i] = f"({s[i]},{s[n - i - 1]})"
            n >>= 1
        return s[0]

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 544. Output Contest Matches is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems