MediumNo. 1718
Construct the Lexicographically Largest Valid Sequence — LeetCode 1718 Python Solution
- Pattern
- Backtracking
- Topics
- Array, 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
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
- Time
- Exponential (worst case)
- Space · auxiliary
- O(depth)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0039 | Combination Sum | Medium |
| 0040 | Combination Sum II | Medium |
| 0046 | Permutations | Medium |
| 0047 | Permutations II | Medium |
| 0051 | N-Queens | Hard |
| 0078 | Subsets | Medium |
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.