Construct the Lexicographically Largest Valid Sequence — LeetCode 1718 Python Solution

MediumArrayBacktracking

Problem: #1718
Pattern: Backtracking
Reading time: 5 min
Source: leetcode.com

The problem

Given an integer n, find a sequence with elements in the range [1, n] that satisfies all of the following: The integer 1 occurs once in the sequence. Each integer between 2 and n occurs twice in the sequence.

Example

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Python solution

Python

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        def dfs(u):
            if u == n * 2:
                return True
            if path[u]:
                return dfs(u + 1)
            for i in range(n, 1, -1):
                if cnt[i] and u + i < n * 2 and path[u + i] == 0:
                    cnt[i] = 0
                    path[u] = path[u + i] = i
                    if dfs(u + 1):
                        return True
                    path[u] = path[u + i] = 0
                    cnt[i] = 2
            if cnt[1]:
                cnt[1], path[u] = 0, 1
                if dfs(u + 1):
                    return True
                path[u], cnt[1] = 0, 1
            return False

        path = [0] * (n * 2)
        cnt = [2] * (n * 2)
        cnt[1] = 1
        dfs(1)
        return path[1:]

Complexity

Measure	Complexity
Time	Exponential (worst case)
Space	O(depth) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1718. Construct the Lexicographically Largest Valid Sequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1718. Construct the Lexicographically Largest Valid Sequence?: LeetCode 1718. Construct the Lexicographically Largest Valid Sequence is rated Medium on LeetCode.
What topics does LeetCode 1718. Construct the Lexicographically Largest Valid Sequence cover?: LeetCode 1718. Construct the Lexicographically Largest Valid Sequence is tagged Array and Backtracking on LeetCode.