544. Output Contest Matches

Approach 1: Merging opposite ends every time

class Solution(object):
    def findContestMatch(self, n):
        """
        https://leetcode.com/problems/output-contest-matches/
        :type n: int
        :rtype: str
        """
        res = map(str, range(1, n+1))
        while n > 1:
            res = ["(" + res[i] + "," + res[n-1-i] + ")" for i in range(n // 2)]
            n //= 2
        return res[0]

For every round we will be joining the weakest and strongest teams. So the way to approach this would be to start with a list of all teams and then each time pair the first and last items and arrange them in their order of merging. This will ensure that the after the first time the pairs are made, they are still sorted in weakest to strongest. Repeat this step until all the pairs are created.

Time Complexity: O(log(N))

Space Complexity: O(N)