LeetCode 1718 - Construct the Lexicographically Largest Valid Sequence

LeetCode Problem 1718

Difficulty: 🟡 Medium
Topics: Array, Backtracking

Solution

Problem Understanding

The problem asks us to construct a special integer sequence using numbers from 1 to n.

The resulting sequence has length 2 * n - 1 because:

• The number 1 appears exactly once.
• Every number from 2 to n appears exactly twice.

That means the total number of elements is:

• 1 occurrence for 1
• 2 * (n - 1) occurrences for numbers 2 through n

So the total length becomes:

$$1 + 2(n - 1) = 2n - 1$$

The key restriction is about distances. For every number i >= 2, if its two occurrences are placed at indices a and b, then:

$$|b - a| = i$$

For example, if we place the number 4 at index 2, then the second 4 must appear at index 6.

The problem also asks for the lexicographically largest valid sequence. Lexicographical order compares sequences from left to right. At the first differing position, the sequence with the larger value is considered larger.

This requirement is extremely important because many valid sequences may exist. We must specifically construct the one that places larger numbers as early as possible.

The constraints are relatively small:

• 1 <= n <= 20

Even though n is small, the number of possible arrangements grows extremely quickly. A naive brute-force permutation search would still be infeasible. This strongly suggests that we need a carefully pruned backtracking solution.

There are several important edge cases to keep in mind:

• n = 1 is the smallest input. The answer is simply [1].
• Large numbers are harder to place because they require large gaps.
• Once positions become fragmented, some remaining numbers may no longer fit.
• Greedy placement alone is not sufficient because an early choice can block all future valid completions.
• The problem guarantees that at least one valid solution always exists.

Approaches

Brute Force Approach

A brute-force solution would attempt to generate every possible sequence of length 2n - 1 using the required counts of each number, then validate whether the distance constraints hold.

The process would look like this:

1. Generate all permutations of the multiset:

• One 1
• Two copies of every number from 2 to n

2. For each permutation:

• Check whether every duplicated number appears exactly i indices apart.

3. Track the lexicographically largest valid sequence.

This approach is correct because it examines every possible candidate arrangement. Eventually it would discover the optimal answer.

However, the search space is enormous. Even for moderate n, the number of permutations becomes astronomically large. Since the sequence length can reach 39, exhaustive permutation generation is completely impractical.

Optimal Approach, Backtracking with Greedy Ordering

The key insight is that we do not need to generate all permutations.

Instead, we can build the sequence incrementally while immediately enforcing the distance constraints.

At each step:

• Find the first empty position.
• Try placing numbers from largest to smallest.
• For numbers greater than 1, place both occurrences simultaneously.
• If placement becomes impossible later, backtrack.

Trying larger numbers first is critical. Since lexicographical order prioritizes earlier positions, placing larger values earlier guarantees that the first complete valid solution we discover is already the lexicographically largest one.

This dramatically reduces the search space because:

• Invalid states are abandoned immediately.
• Distance rules are enforced during construction.
• Greedy descending order avoids exploring many smaller lexicographical candidates.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((2n)!)	O((2n)!)	Generates and validates all permutations
Optimal	O(2^n) approximately	O(n)	Backtracking with strong pruning and greedy ordering

The exact complexity of backtracking is difficult to express precisely because pruning eliminates most branches in practice.

Algorithm Walkthrough

Step 1: Initialize the Sequence

Create an array called sequence of length 2 * n - 1, initially filled with 0.

A value of 0 means the position is still empty.

Also create a used array to track whether a number has already been fully placed.

Step 2: Define the Recursive Backtracking Function

The recursive function attempts to fill the sequence from left to right.

The function receives the current index being processed.

Step 3: Skip Already Filled Positions

Sometimes a previous placement fills multiple positions simultaneously.

If the current index is already occupied, recursively move to the next index.

Step 4: Detect Completion

If the index reaches the sequence length, every position has been filled successfully.

Return True to indicate success.

Step 5: Try Numbers from Largest to Smallest

Iterate from n down to 1.

This ordering is essential because we want the lexicographically largest sequence.

Trying larger numbers first ensures earlier positions contain the largest possible values.

Step 6: Skip Already Used Numbers

If a number has already been placed:

• Skip it.
• Continue to the next candidate.

Step 7: Handle Number 1 Separately

The number 1 appears only once.

If the current position is empty:

• Place 1
• Mark it as used
• Recurse to the next position

If recursion succeeds, return True.

Otherwise:

• Undo the placement
• Continue searching

Step 8: Handle Numbers Greater Than 1

For any number num > 1, we must place two copies exactly num indices apart.

If we place the first copy at index i, the second copy must be at:

$$i + num$$

Before placement, verify:

• i + num is inside the array bounds
• Both positions are empty

If valid:

• Place the number in both positions
• Mark it as used
• Recurse

If recursion fails:

• Remove both placements
• Mark the number unused again

Step 9: Backtrack if Necessary

If no number can be placed successfully at the current position:

• Return False

This signals the caller to undo previous decisions and try another arrangement.

Why it works

The algorithm always maintains a valid partial sequence. Every placement immediately satisfies the distance requirement, so invalid configurations are never allowed to continue.

Because numbers are tried in descending order, the search explores lexicographically larger prefixes before smaller ones. The first complete valid sequence found is therefore guaranteed to be the lexicographically largest valid sequence.

Backtracking guarantees completeness because every valid arrangement is eventually explored unless pruned by an already violated constraint.

Python Solution

from typing import List

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        length = 2 * n - 1
        sequence = [0] * length
        used = [False] * (n + 1)

        def backtrack(index: int) -> bool:
            if index == length:
                return True

            if sequence[index] != 0:
                return backtrack(index + 1)

            for num in range(n, 0, -1):
                if used[num]:
                    continue

                if num == 1:
                    sequence[index] = 1
                    used[1] = True

                    if backtrack(index + 1):
                        return True

                    sequence[index] = 0
                    used[1] = False
                else:
                    second_index = index + num

                    if (
                        second_index < length
                        and sequence[index] == 0
                        and sequence[second_index] == 0
                    ):
                        sequence[index] = num
                        sequence[second_index] = num
                        used[num] = True

                        if backtrack(index + 1):
                            return True

                        sequence[index] = 0
                        sequence[second_index] = 0
                        used[num] = False

            return False

        backtrack(0)
        return sequence

The implementation starts by creating the target sequence array and a used array. The sequence is initialized with zeroes to indicate empty positions.

The recursive backtrack function attempts to fill the sequence from left to right. If a position is already occupied, the recursion skips it because a previous placement already handled that slot.

The algorithm always tries numbers in descending order. This is the core mechanism that guarantees lexicographical maximality.

For numbers greater than 1, the implementation computes the required second index using index + num. Both positions must be valid and empty before placement can occur.

If recursive exploration fails, the algorithm removes the placements and restores the previous state. This undo operation is the essence of backtracking.

Eventually, the first complete valid sequence is returned.

Go Solution

func constructDistancedSequence(n int) []int {
	length := 2*n - 1
	sequence := make([]int, length)
	used := make([]bool, n+1)

	var backtrack func(int) bool

	backtrack = func(index int) bool {
		if index == length {
			return true
		}

		if sequence[index] != 0 {
			return backtrack(index + 1)
		}

		for num := n; num >= 1; num-- {
			if used[num] {
				continue
			}

			if num == 1 {
				sequence[index] = 1
				used[1] = true

				if backtrack(index + 1) {
					return true
				}

				sequence[index] = 0
				used[1] = false
			} else {
				secondIndex := index + num

				if secondIndex < length &&
					sequence[index] == 0 &&
					sequence[secondIndex] == 0 {

					sequence[index] = num
					sequence[secondIndex] = num
					used[num] = true

					if backtrack(index + 1) {
						return true
					}

					sequence[index] = 0
					sequence[secondIndex] = 0
					used[num] = false
				}
			}
		}

		return false
	}

	backtrack(0)
	return sequence
}

The Go implementation closely mirrors the Python solution. Slices are used instead of dynamic Python lists.

The recursive function is declared as a closure so it can access sequence, used, and length without requiring additional parameters.

Go does not require special handling for integer overflow here because all values remain extremely small under the problem constraints.

Unlike Python, Go does not have implicit boolean truthiness, so all conditions are written explicitly.

Worked Examples

Example 1

Input:

n = 3

Sequence length:

2 * 3 - 1 = 5

Initial state:

Index	0	1	2	3	4
Value	0	0	0	0	0

Step 1

Try placing 3 at index 0.

Second occurrence must be at:

0 + 3 = 3

Valid placement.

Index	0	1	2	3	4
Value	3	0	0	3	0

Step 2

Move to index 1.

Try 3, already used.

Try 2.

Second occurrence would be:

1 + 2 = 3

But index 3 is occupied.

Try 1.

Index	0	1	2	3	4
Value	3	1	0	3	0

Step 3

Move to index 2.

Try 2.

Second occurrence:

2 + 2 = 4

Both positions are empty.

Index	0	1	2	3	4
Value	3	1	2	3	2

All positions are filled.

Final answer:

[3,1,2,3,2]

Example 2

Input:

n = 5

Sequence length:

9

Initial state:

Index	0	1	2	3	4	5	6	7	8
Value	0	0	0	0	0	0	0	0	0

Step 1

Place 5 at indices 0 and 5.

Index	0	1	2	3	4	5	6	7	8
Value	5	0	0	0	0	5	0	0	0

Step 2

At index 1, place 3 at indices 1 and 4.

Index	0	1	2	3	4	5	6	7	8
Value	5	3	0	0	3	5	0	0	0

Step 3

At index 2, try 4.

Second occurrence:

2 + 4 = 6

Valid.

Index	0	1	2	3	4	5	6	7	8
Value	5	3	4	0	3	5	4	0	0

Step 4

At index 3, place 1.

Index	0	1	2	3	4	5	6	7	8
Value	5	3	4	1	3	5	4	0	0

Step 5

At index 7, place 2.

Second occurrence:

7 + 2 = 9

Out of bounds.

Backtrack.

Eventually the algorithm finds:

[5,3,1,4,3,5,2,4,2]

which is the lexicographically largest valid sequence.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n) approximately	Backtracking explores combinations with pruning
Space	O(n)	Recursion stack and bookkeeping arrays

The algorithm uses recursive backtracking, so the exact complexity depends on how much pruning occurs. In practice, the constraints are small enough that this solution performs efficiently.

The recursion depth is at most 2n - 1, and the auxiliary structures only store arrays proportional to n.

Test Cases

from typing import List

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        length = 2 * n - 1
        sequence = [0] * length
        used = [False] * (n + 1)

        def backtrack(index: int) -> bool:
            if index == length:
                return True

            if sequence[index] != 0:
                return backtrack(index + 1)

            for num in range(n, 0, -1):
                if used[num]:
                    continue

                if num == 1:
                    sequence[index] = 1
                    used[1] = True

                    if backtrack(index + 1):
                        return True

                    sequence[index] = 0
                    used[1] = False
                else:
                    second_index = index + num

                    if (
                        second_index < length
                        and sequence[index] == 0
                        and sequence[second_index] == 0
                    ):
                        sequence[index] = num
                        sequence[second_index] = num
                        used[num] = True

                        if backtrack(index + 1):
                            return True

                        sequence[index] = 0
                        sequence[second_index] = 0
                        used[num] = False

            return False

        backtrack(0)
        return sequence

def is_valid(sequence, n):
    positions = {}

    for i, value in enumerate(sequence):
        positions.setdefault(value, []).append(i)

    if positions[1] and len(positions[1]) != 1:
        return False

    for num in range(2, n + 1):
        if len(positions.get(num, [])) != 2:
            return False

        a, b = positions[num]

        if abs(b - a) != num:
            return False

    return True

solution = Solution()

# Example 1
result = solution.constructDistancedSequence(3)
assert result == [3, 1, 2, 3, 2]  # provided example

# Example 2
result = solution.constructDistancedSequence(5)
assert result == [5, 3, 1, 4, 3, 5, 2, 4, 2]  # provided example

# Minimum input
result = solution.constructDistancedSequence(1)
assert result == [1]  # smallest valid case

# Small case validation
result = solution.constructDistancedSequence(2)
assert is_valid(result, 2)  # validates correctness for n=2

# Medium case validation
result = solution.constructDistancedSequence(4)
assert is_valid(result, 4)  # validates correctness for n=4

# Larger case validation
result = solution.constructDistancedSequence(7)
assert is_valid(result, 7)  # stress test for larger recursion depth

# Maximum constraint
result = solution.constructDistancedSequence(20)
assert is_valid(result, 20)  # verifies maximum allowed input

Test	Why
n = 1	Verifies smallest possible input
n = 2	Tests basic duplicate-distance handling
n = 3	Verifies provided example output
n = 4	Tests moderate recursive branching
n = 5	Verifies larger provided example
n = 7	Tests deeper recursion and pruning
n = 20	Validates performance at maximum constraint

Edge Cases

Edge Case 1, n = 1

This is the smallest possible input. The sequence length becomes 1, and only the number 1 must be placed.

A buggy implementation might incorrectly assume every number appears twice or attempt to place a second occurrence for 1.

The implementation handles this correctly by treating 1 as a special case and placing it only once.

Edge Case 2, Large Numbers Near the End of the Array

Suppose we try placing a large number near the right side of the sequence.

For example, if n = 5 and we attempt to place 5 at index 6, the second occurrence would need to be at index 11, which is outside the array.

Without careful bounds checking, this would cause index errors.

The implementation prevents this by verifying:

second_index < length

before placement.

Edge Case 3, Fragmented Empty Slots

As the sequence fills up, empty positions may become scattered in ways that prevent remaining numbers from fitting.

For example, there may be isolated empty cells where a large number cannot satisfy its distance requirement.

A greedy algorithm without backtracking would fail permanently in such situations.

The implementation solves this by undoing invalid placements and exploring alternative arrangements through recursion.

Edge Case 4, Lexicographical Ordering

Multiple valid sequences often exist.

For example, when n = 3:

[2,3,2,1,3]

is valid, but:

[3,1,2,3,2]

is lexicographically larger.

If numbers were tried in ascending order, the algorithm would likely return a smaller valid sequence first.

The implementation guarantees the correct answer by always trying numbers from n down to 1.