NeetCode #511LC-1718MediumBacktracking
← Back to All Problems#511 · #1718 · Construct the Lexicographically Largest Valid Sequence(构建字典序最大的可行序列)
📌 Problem Statement & Constraints
Given an integer
n, construct the lexicographically largest sequence of length 2n - 1 containing two occurrences of each number from 1 to n, and one occurrence of 1, such that the two occurrences of x (for x > 1) are exactly x positions apart. Constraints: 1 <= n <= 20.💡 Core Algorithmic Approaches
- Place numbers from largest to smallest, which greedily maximises the lexicographic order.
- For
x > 1, placing it at positionialso occupies positioni + x; both must be empty. - For
x == 1, only one slot is needed (it is its own partner). - Backtrack on the first empty position: try the largest unused value that fits, and recurse.
💻 Benchmark Python3 Implementation
class Solution:
def constructDistancedSequence(self, n: int) -> List[int]:
size = 2 * n - 1
res = [0] * size
used = [False] * (n + 1)
def dfs(i: int) -> bool:
if i == size:
return True # fully placed
if res[i] != 0: # already filled
return dfs(i + 1)
for v in range(n, 0, -1): # largest first -> lexicographically largest
if used[v]:
continue
if v == 1:
used[1] = True
res[i] = 1
if dfs(i + 1):
return True
res[i] = 0
used[1] = False
elif i + v < size and res[i + v] == 0:
used[v] = True
res[i] = res[i + v] = v
if dfs(i + 1):
return True
res[i] = res[i + v] = 0
used[v] = False
return False
dfs(0)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n!) worst case, but the greedy ordering and early success make it fast in practice.
💾 Space Complexity
O(n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Trying values from smallest to largest: that yields the lexicographically smallest, not largest.
- Forgetting the
i + v < sizebounds check: the second occurrence could fall outside the array. - Treating 1 like the others: it needs only one slot, since both occurrences coincide.
- Skipping the
res[i] != 0check: an already-filled position must be skipped, not overwritten.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.