1718. Construct the Lexicographically Largest Valid Sequence

Given an integer n, find a sequence that satisfies all of the following:

• The integer 1 occurs once in the sequence.
• Each integer between 2 and n occurs twice in the sequence.
• For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

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 01:

#include <vector>

class Solution {
public:
    // Helper function to find the largest lexicographical sequence
    bool findLargestSequence(std::vector<int>& sequence, std::vector<bool>& isUsed, int index, int n) {
        if (index == (2 * n - 1)) {
            return true;
        }
        if (sequence[index] != 0) {
            return findLargestSequence(sequence, isUsed, index + 1, n);
        }
        
        for (int num = n; num >= 1; --num) {
            if (isUsed[num]) continue;
            isUsed[num] = true;
            sequence[index] = num;

            if (num == 1) {
                if (findLargestSequence(sequence, isUsed, index + 1, n)) return true;
            } 
            else if ((index + num) < (2 * n - 1) && sequence[index + num] == 0) {
                sequence[index + num] = num;
                if (findLargestSequence(sequence, isUsed, index + 1, n)) return true;
                sequence[index + num] = 0; 
            }

            isUsed[num] = false; 
            sequence[index] = 0;
        }
        return false;
    }

    // Main function to construct the lexicographically largest sequence
    std::vector<int> constructDistancedSequence(int n) {
        std::vector<int> sequence(2 * n - 1, 0);
        std::vector<bool> isUsed(n + 1, false);
        findLargestSequence(sequence, isUsed, 0, n);
        return sequence;
    }
};

class Solution:
    # Helper function to find the largest lexicographical sequence
    def findLargestSequence(self, sequence, isUsed, index, n):
        if index == (2 * n - 1):
            return True
        if sequence[index] != 0:
            return self.findLargestSequence(sequence, isUsed, index + 1, n)

        for num in range(n, 0, -1):
            if isUsed[num]:
                continue
            isUsed[num] = True
            sequence[index] = num

            if num == 1:
                if self.findLargestSequence(sequence, isUsed, index + 1, n):
                    return True
            elif (index + num) < (2 * n - 1) and sequence[index + num] == 0:
                sequence[index + num] = num
                if self.findLargestSequence(sequence, isUsed, index + 1, n):
                    return True
                sequence[index + num] = 0  

            isUsed[num] = False  
            sequence[index] = 0  

        return False

    # Main function to construct the lexicographically largest sequence
    def constructDistancedSequence(self, n):
        sequence = [0] * (2 * n - 1)
        isUsed = [False] * (n + 1)
        self.findLargestSequence(sequence, isUsed, 0, n)
        return sequence

Time Complexity:

• Worst Case:

  The function uses backtracking to generate the lexicographically largest sequence. In the worst case, it explores all possible placements of numbers in the sequence. The number of states to explore is approximately \( O(n!) \), leading to a time complexity of \( O(n!) \).

Space Complexity:

• Recursive Stack:

  The recursive function calls contribute to a space complexity of \( O(n) \) due to the depth of the recursion tree.

• Auxiliary Space:

  The algorithm uses two extra arrays: sequence of size \( O(2n) \) and isUsed of size \( O(n) \), leading to an additional space usage of \( O(n) \).

• Total Space Complexity:

  Combining both, the overall space complexity is \( O(n) \).