Construct the Lexicographically Largest Valid Sequence

Problem Statement

Given an integer n, your task is to construct a sequence using numbers from 1 to n adhering to specific conditions. In the sequence:

• The number 1 should appear only once.
• Every number from 2 to n must appear exactly twice.
• For each number i ranging from 2 to n, the distance between its two occurrences should be precisely i. The distance is defined by the absolute difference between their positions in the sequence.

Your goal is to ensure that this constructed sequence is the lexicographically largest possible sequence meeting the above criteria. A sequence is considered lexicographically larger if at the first differing position, it possesses a larger number compared to another sequence of the same length. This task is guaranteed to have a solution within the given constraints.

Examples

Example 1

Input:

n = 3

Output:

[3,1,2,3,2]

Explanation:

[2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2

Input:

n = 5

Output:

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

Constraints

• 1 <= n <= 20

Approach and Intuition

To generate the lexicographically largest sequence satisfying the given conditions, it's beneficial to strategically place the numbers starting from the largest. Here's a step-by-step breakdown of the approach:

1. Start by initializing an empty sequence and a placement tracker to ensure that each condition about the distances is met effectively.
2. Iterate from the largest number (n) down to 2:
   • Attempt to place each occurrence of the number i such that the first occurrence is as far to the right as possible but leaves enough space for the second occurrence to satisfy the distance condition i.
   • If placing i at certain positions results in a conflict (i.e., an overlap with another number or not enough space), adjust its position.
3. Once all numbers from 2 to n are placed according to their required distances, place the number 1 in the remaining slot, which should be the first unfilled position from the left due to its single occurrence requirement.
4. You may utilize a backtracking method combined with these strategic placements:
   • Start filling the sequence from the first position possible for the largest number and backtrack whenever a placement violates the sequence conditions or leads to a dead end.
   • The search will continue until a valid sequence is constructed that adheres to all the conditions.

This thoughtful approach, beginning from the largest and placing strategically backward, should yield the lexicographically largest sequence as it prioritizes larger numbers to fill earlier and more significant positions in the sequence, wherever applicable.

Solutions

class Solution {
public:
    vector<int> createSequence(int n) {
        vector<int> sequence(2 * n - 1, 0);
        vector<bool> used(n + 1, false);
        backtrack(0, sequence, used, n);
        return sequence;
    }
    
private:
    bool backtrack(int idx, vector<int>& sequence, vector<bool>& used, int n) {
        if (idx == sequence.size()) {
            return true;
        }
        if (sequence[idx] != 0) {
            return backtrack(idx + 1, sequence, used, n);
        }
        for (int num = n; num > 0; --num) {
            if (used[num]) continue;
    
            used[num] = true;
            sequence[idx] = num;
    
            if (num == 1) {
                if (backtrack(idx + 1, sequence, used, n)) {
                    return true;
                }
            } else if (idx + num < sequence.size() && sequence[idx + num] == 0) {
                sequence[idx + num] = num;
                if (backtrack(idx + 1, sequence, used, n)) {
                    return true;
                }
                sequence[idx + num] = 0;
            }
    
            sequence[idx] = 0;
            used[num] = false;
        }
        return false;
    }
};