1718. Construct the Lexicographically Largest Valid Sequence

Description

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

 

Solutions

Solution: Backtracking

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @return {number[]}
 */
const constructDistancedSequence = function (n) {
  const size = n * 2 - 1;
  const result = [];
  const visited = new Set();
  const constructSequence = (index = 0) => {
    if (index >= size) return true;
    if (result[index]) return constructSequence(index + 1);

    for (let num = n; num > 0; num--) {
      if (visited.has(num)) continue;
      result[index] = num;
      visited.add(num);
      if (num === 1 && constructSequence(index + 1)) return true;
      if (index + num < size && !result[index + num]) {
        result[index + num] = num;
        if (constructSequence(index + 1)) return true;
        result[index + num] = 0;
      }
      result[index] = 0;
      visited.delete(num);
    }
    return false;
  };

  constructSequence();
  return result;
};