Construct the Lexicographically Largest Valid Sequence: Backtracking

Given an integer n, find a sequence of length 2 * n - 1 that satisfies three rules: the number 1 appears exactly once, every integer i between 2 and n (inclusive) appears exactly twice, and the two occurrences of each i have exactly i elements between them. Among all valid sequences, return the lexicographically largest one.

This is LeetCode 1718: Construct the Lexicographically Largest Valid Sequence. It combines constraint-based placement with greedy ordering, making it a clean exercise in backtracking with purpose.

For n = 3, the answer is [3, 1, 2, 3, 2].

Why this problem matters

This problem sits at the intersection of two important ideas: constraint satisfaction and lexicographic optimization. You are not just finding any valid arrangement. You need the largest one, which means you cannot simply enumerate all solutions and sort them. The greedy ordering baked into the backtracking is what makes it efficient.

If you have solved N-Queens, you already know how to place items on a board while respecting constraints. This problem uses the same backtracking skeleton but adds a twist: instead of finding all solutions, you want exactly one, and you want it to be the lexicographically largest. The greedy "try biggest first" strategy guarantees that the first valid sequence you find is the answer.

This pattern of greedy backtracking, where the order you try candidates determines the quality of the first solution, shows up in many optimization problems. Once you internalize it here, you can apply the same idea anywhere you need "the best valid arrangement."

The key insight

Build the sequence left to right. At each empty position, try placing the largest unused number first. For any number i > 1, placing it at position j forces the second copy at position j + i. If that second position is out of bounds or already occupied, skip this number and try the next one down. For the number 1, you only need one position, so just place it and move on.

Because you always try the largest number first at every position, the first complete sequence you find is guaranteed to be the lexicographically largest valid one. There is no need to find all solutions and compare them.

The algorithm:

1. Create an array of 2 * n - 1 zeros (empty slots) and a used set.
2. Start at position 0. If the current position is already filled, skip to the next.
3. For each number from n down to 1, if it has not been used:
   • If the number is 1, place it at the current position.
   • Otherwise, check if position j + i is in bounds and empty. If so, place the number at both positions.
4. Recurse to the next position. If the recursion succeeds, you are done.
5. If no number works at this position, undo your placement and return false (backtrack).

The solution

def construct_distanced_sequence(n: int) -> list[int]:
    length = 2 * n - 1
    result = [0] * length
    used = [False] * (n + 1)

    def backtrack(pos):
        if pos == length:
            return True
        if result[pos] != 0:
            return backtrack(pos + 1)
        for num in range(n, 0, -1):
            if used[num]:
                continue
            if num == 1:
                result[pos] = 1
                used[1] = True
                if backtrack(pos + 1):
                    return True
                result[pos] = 0
                used[1] = False
            else:
                if pos + num < length and result[pos + num] == 0:
                    result[pos] = num
                    result[pos + num] = num
                    used[num] = True
                    if backtrack(pos + 1):
                        return True
                    result[pos] = 0
                    result[pos + num] = 0
                    used[num] = False
        return False

    backtrack(0)
    return result

Let's walk through the key parts.

The outer function creates a result array filled with zeros and a used array to track which numbers have been placed. Then it kicks off backtrack(0).

The base case is pos == length. If you have moved past the last position, every slot is filled and you have a valid sequence. Return True.

If the current position is already occupied (because a previous number's second copy landed here), skip it by recursing to pos + 1. This is important because not every position triggers a new placement decision.

The core loop tries numbers from n down to 1. This descending order is the greedy part. By trying the largest number first, the first valid sequence you complete is the lexicographically largest.

For num == 1, you only place it once since 1 appears exactly once in the sequence. For any other num, you check that the second position pos + num is within bounds and empty. If both conditions hold, you place num at both positions, mark it as used, and recurse. If the recursion fails, you undo everything (set both positions back to 0, mark the number as unused) and try the next smaller number.

If no number works at the current position, return False to trigger backtracking in the caller.

Visual walkthrough

Let's trace through the algorithm for n = 3. The sequence has 2 * 3 - 1 = 5 slots.

The key moment is step 3. When you try to place 2 at position 1, its second copy would need to go at position 3, which is already taken by 3. This forces you to try position 2 instead, where the second copy lands at position 4. That single conflict and recovery is the essence of backtracking: try, fail, undo, try the next option.

Complexity analysis

Time is O(n!) in the worst case. At each position, you try up to n numbers, and there are 2 * n - 1 positions. However, the constraints prune most branches aggressively. Placing a number at one position immediately fills a second position too, which dramatically reduces the search space. In practice, the algorithm runs fast for the constraint range (n up to 20).

Space is O(n). The result array has 2 * n - 1 entries, and the used array has n + 1 entries. The recursion stack goes at most 2 * n - 1 levels deep. All of these are O(n).

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

1. Constraint-based backtracking

The choose-explore-unchoose skeleton with placement constraints:

def backtrack(pos):
    if pos == length:
        return True
    if result[pos] != 0:
        return backtrack(pos + 1)
    for num in candidates:
        if can_place(num, pos):
            place(num, pos)
            if backtrack(pos + 1):
                return True
            remove(num, pos)
    return False

This is the same skeleton used in N-Queens, where you place queens row by row and check column and diagonal constraints. The only difference is the specific constraint: here, placing number i at position j forces a second placement at j + i. The skeleton itself is identical.

2. Greedy ordering for lexicographic optimization

Trying candidates in descending order guarantees that the first valid solution is the lexicographically largest. This is a general technique: if you want the "best" solution according to some ordering, sort your candidates so that the preferred option is tried first. Combined with early termination (return True as soon as you find a solution), this avoids exploring the entire search space.

The same idea applies to any problem that asks for "the largest" or "the smallest" valid arrangement. Sort your candidates accordingly and let the backtracking find the first solution.

Edge cases

Before submitting, check these:

• n = 1: The sequence has length 1 and contains just [1]. The algorithm handles this because 1 is placed once and the recursion immediately hits the base case.
• n = 2: The sequence is [2, 1, 2]. The number 2 goes at positions 0 and 2 (distance 2), and 1 fills position 1.
• Large n: For n = 20, the sequence has 39 positions. The constraints prune the search tree heavily, so the algorithm finishes quickly despite the factorial worst case.
• Backtracking depth: Even though the recursion can go 2 * n - 1 levels deep, each level does constant work (try a number, place or skip). Stack overflow is not a concern for n up to 20.

From understanding to recall

You understand the backtracking skeleton. You see how the greedy ordering ensures the first solution is optimal. You can trace through the placement of 3, then 2, then 1 for a small example. But can you write this solution from scratch in under three minutes?

The tricky parts are the details: the special case for 1 (placed once, not twice), the bounds check on pos + num, and remembering to skip already-filled positions with backtrack(pos + 1). These are not hard individually, but under interview pressure, it is easy to forget one of them.

Spaced repetition makes these details automatic. You practice writing the constraint-based backtracking skeleton with the greedy ordering until the code flows without hesitation. After a few rounds, the pattern is locked in. You see "construct the largest valid arrangement" and you know exactly what to write.

Related posts

• N-Queens - Classic constraint-based backtracking on a board
• Permutations - Backtracking template for generating arrangements
• Combinations - Systematic backtracking with pruning

CodeBricks breaks this problem into its constraint-based backtracking building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a placement problem shows up in your interview, you do not think about it. You just write it.