Problem statement

https://leetcode.com/problems/output-contest-matches/

Solution

We can generate the order of numbers first and then put brackets in right places. For example, we can generate [1,8,4,5,2,7,3,6] first and pattern (((#,#),(#,#)),((#,#),(#,#))) and then put our numbers into pattern. How we can generate numbers? Look at [1,4,2,3], then we need to put after each number k, number 9-k, similar for next steps.

Complexity

Time and space complexity will be O(n), because we do O(1) + O(2) + O(4) + ... + O(n/2) + O(n) operations. Space complexity is O(n) as well.

Code

class Solution:
    def findContestMatch(self, n):
        matches = [1, 2]
        pattern = "(#,#)"
        for step in range(2,int(log2(n))+1):
            pattern = pattern.replace("#", "(#,#)")
            matches = list(chain(*[[i, (1<<step)-i + 1] for i in matches]))
            
        res, it = "", 0
        for symb in pattern:
            if symb != "#":
                res += symb
            else:
                res += str(matches[it])
                it += 1
        
        return res