LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

Solution is a greedy recursion. Iterate in reverse order to make sure to get the largest solution first.

function constructDistancedSequence(n: number): number[] {
    const size = 2 * n - 1;
    const result: number[] = new Array(size).fill(0);
    const used: boolean[] = new Array(n + 1).fill(false);
    function backtrack(index: number): boolean {
        if (index === size) return true; // If we filled the array, return success
        if (result[index] !== 0) return backtrack(index + 1); // Skip filled positions
        for (let num = n; num >= 1; num--) { // Try from largest to smallest
            if (used[num]) continue;
            if (num === 1) {
                // Place 1 (only once)
                result[index] = 1;
                used[1] = true;
                if (backtrack(index + 1)) return true;
                used[1] = false;
                result[index] = 0;
            } else {
                // Place num at index and index + num (if valid)
                if (index + num < size && result[index + num] === 0) {
                    result[index] = result[index + num] = num;
                    used[num] = true;
                    if (backtrack(index + 1)) return true;
                    used[num] = false;
                    result[index] = result[index + num] = 0;
                }
            }
        }
        return false;
    }
    backtrack(0);
    return result;
}