Construct the Lexicographically Largest Valid Sequence — Medium Problem & Solution

Problem statement

Build a sequence of length 2n - 1 that satisfies all of these rules:

• The value 1 appears exactly once.
• Every value v from 2 to n appears exactly twice, and its two occurrences are exactly v positions apart (if they sit at indices i < j, then j - i == v).
• No other values appear.

Among all such sequences, return the lexicographically largest one — the one that is larger at the first index where two sequences differ. A valid sequence always exists.

Example 1

Input: n = 3
Output: [3,1,2,3,2]
Explanation: `[2,3,2,1,3]` is valid too, but it is smaller at index 0.

Example 2

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Example 3

Input: n = 1
Output: [1]

Constraints

• 1 <= n <= 20

How to solve Construct the Lexicographically Largest Valid Sequence

Greedy with backtracking: the leftmost position is the most significant, so at each empty position try values from n down to 1, and accept the first complete assignment.

Approach

1. Create an array of 2n - 1 zeros and a used flag per value.
2. dfs(pos): if pos is past the end, succeed; if res[pos] is already filled (by an earlier pair), move on to pos + 1.
3. Otherwise for v from n down to 1, if v is unused and its partner cell (pos + v, or nothing for v = 1) is free and inside the array, place it, recurse, and undo on failure.
4. Return the array after dfs(0) succeeds.

Why it works

The search visits complete sequences in decreasing lexicographic order: at each position it commits to the largest value that still admits a completion. So the first sequence it finishes is the largest one. In practice the greedy choice almost never needs to backtrack far.

Complexity

• Time — Exponential in the worst case; immediate for every n ≤ 20
• Space — O(n)

Pitfalls

• The two copies of v are v apart — indices i and i + v — not v cells between them.
• Skip positions already filled by the second copy of an earlier value.
• The value 1 occupies a single cell; treating it like the others breaks the length.

Reference solution

Python

from typing import List

def constructDistancedSequence(n: int) -> List[int]:
    size = 2 * n - 1
    res = [0] * size
    used = [False] * (n + 1)

    def dfs(pos):
        if pos == size:
            return True
        if res[pos]:
            return dfs(pos + 1)
        for v in range(n, 0, -1):
            if used[v]:
                continue
            other = pos if v == 1 else pos + v
            if other >= size or res[other]:
                continue
            res[pos] = v
            res[other] = v
            used[v] = True
            if dfs(pos + 1):
                return True
            res[pos] = 0
            res[other] = 0
            used[v] = False
        return False

    dfs(0)
    return res

JavaScript

var constructDistancedSequence = function(n) {
    var size = 2 * n - 1;
    var res = new Array(size).fill(0);
    var used = new Array(n + 1).fill(false);
    var dfs = function(pos) {
        if (pos === size) return true;
        if (res[pos] !== 0) return dfs(pos + 1);
        for (var v = n; v >= 1; v--) {
            if (used[v]) continue;
            var other = v === 1 ? pos : pos + v;
            if (other >= size || res[other] !== 0) continue;
            res[pos] = v;
            res[other] = v;
            used[v] = true;
            if (dfs(pos + 1)) return true;
            res[pos] = 0;
            res[other] = 0;
            used[v] = false;
        }
        return false;
    };
    dfs(0);
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium
• Subsets II Medium