⚡Flashcard Drill➔
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

  1. Place numbers from largest to smallest, which greedily maximises the lexicographic order.
  2. For x > 1, placing it at position i also occupies position i + x; both must be empty.
  3. For x == 1, only one slot is needed (it is its own partner).
  4. 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 < size bounds 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] != 0 check: 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems