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 occurren

constructDistancedSequence.js

/**
 * @param {number} n
 * @return {number[]}
 */
var constructDistancedSequence = function(n) {
    // Initialize the sequence array with 0s and an array to track placed numbers
    const seq = new Array(n * 2 - 1).fill(0), isPlaced = new Array(n + 1).fill(false);
    // Mark index 0 as placed (not used in actual sequence)
    isPlaced[0] = true;

    // Recursive function to build the sequence
    const build = (pos) => {
        // If the entire sequence is filled, return true
        if (pos === seq.length) {
            return true;
        }

        // If the current position is already filled, move to the next position
        if (seq[pos] !== 0) {
            return build(pos + 1);
        }

        // Try placing numbers from n to 1 at the current position
        for (let i = n; i >= 1; i--) {
            // Skip if the number is already placed
            if (isPlaced[i]) continue;

            // Skip if the number is greater than 1 and its corresponding position is not empty
            if (i > 1 && seq[pos + i] !== 0) continue;

            // Place the number at the current position
            seq[pos] = i;
            if (i > 1) seq[pos + i] = i;
            isPlaced[i] = true;

            // Recursively build the rest of the sequence
            if (build(pos + 1)) return true;

            // Backtrack if placement does not lead to a solution
            isPlaced[i] = false;
            seq[pos] = 0;
            if (i > 1) seq[pos + i] = 0;
        }

        // Return false if no valid placement is found
        return false;
    }

    // Start building the sequence from position 0
    build(0);

    // Return the constructed sequence
    return seq;
};