Today’s problem

https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description/

Intuition

This question requires you to find a solution according to the requirements.

Approach

Note that $N \le 20$, so we can use a brute search to find the answer.

Complexity

Time complexity: $O(N^N)$, N is the same definition as the question.
Space complexity: $O(N)$, N is the same definition as the question.

Code

Normal dfs solution

class Solution:
    def dfs(self, pos, n, vis, pls):
        if pos == 2 * n - 1:
            return pls
        # if we enumerate to the end of the sequence, then we can return the answer.

        if pls[pos] != 0:
            return self.dfs(pos + 1, n, vis, pls)
        # if we place a number in the current position, then we can move to the next position.
        for i in range(n, 1, -1):
        # we enumerate from large to small so that we can get the largest sequence.
            if vis[i]:
                continue
            # if we use this number, then pass.
            if pos + i < 2 * n - 1 and pls[pos + i] == 0:
                pls[pos] = i
                pls[pos + i] = i
                vis[i] = True
                # put the number into the slot if it is available.
                ret = self.dfs(pos + 1, n, vis, pls)
                if ret is not None:
                    return ret
                vis[i] = False
                pls[pos] = 0
                pls[pos + i] = 0

        if vis[1]:
            return None
        vis[1] = True
        pls[pos] = 1
        ret = self.dfs(pos + 1, n, vis, pls)
        if ret is not None:
            return ret
        vis[1] = False
        pls[pos] = 0
        # special check for 1 becuase 1 only puts into one slot.

        return None

    def constructDistancedSequence(self, n: int) -> List[int]:
        pls = [0] * (2 * n - 1)
        # pls is the sequence that we place numbers        
        vis = [0] * (n+1)
        # visit is the sequence we test whether a number exists in the current sequence or not.
        return self.dfs(0, n, vis, pls)

Faster solution for future use

Note that the solution will not change when we input the same number, therefore, we can just store the answer we get and output it for every query.

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        ans = [
            [1],
            [2,1,2],
            [3,1,2,3,2],
            [4,2,3,2,4,3,1],
            [5,3,1,4,3,5,2,4,2],
            [6,4,2,5,2,4,6,3,5,1,3],
            [7,5,3,6,4,3,5,7,4,6,2,1,2],
            [8,6,4,2,7,2,4,6,8,5,3,7,1,3,5],
            [9,7,5,3,8,6,3,5,7,9,4,6,8,2,4,2,1],
            [10,8,6,9,3,1,7,3,6,8,10,5,9,7,4,2,5,2,4],
            [11,9,10,6,4,1,7,8,4,6,9,11,10,7,5,8,2,3,2,5,3],
            [12,10,11,7,5,3,8,9,3,5,7,10,12,11,8,6,9,2,4,2,1,6,4],
            [13,11,12,8,6,4,9,10,1,4,6,8,11,13,12,9,7,10,3,5,2,3,2,7,5],
            [14,12,13,9,7,11,4,1,10,8,4,7,9,12,14,13,11,8,10,6,3,5,2,3,2,6,5],
            [15,13,14,10,8,12,5,3,11,9,3,5,8,10,13,15,14,12,9,11,7,4,6,1,2,4,2,7,6],
            [16,14,15,11,9,13,6,4,12,10,1,4,6,9,11,14,16,15,13,10,12,8,5,7,2,3,2,5,3,8,7],
            [17,15,16,12,10,14,7,5,3,13,11,3,5,7,10,12,15,17,16,14,9,11,13,8,6,2,1,2,4,9,6,8,4],
            [18,16,17,13,11,15,8,14,4,2,12,2,4,10,8,11,13,16,18,17,15,14,12,10,9,7,5,3,6,1,3,5,7,9,6],
            [19,17,18,14,12,16,9,15,6,3,13,1,3,11,6,9,12,14,17,19,18,16,15,13,11,10,8,4,5,7,2,4,2,5,8,10,7],
            [20,18,19,15,13,17,10,16,7,5,3,14,12,3,5,7,10,13,15,18,20,19,17,16,12,14,11,9,4,6,8,2,4,2,1,6,9,11,8]
        ]
        return ans[n - 1]

Today’s problem#

Intuition#

Approach#

Complexity#

Code#

Normal dfs solution#

Faster solution for future use#