Robert Baindourov

NodeJS, ReactJS, ElectronJS - Web Software Architect

This article explains the solution for LeetCode 1718: Construct the Lexicographically Largest Valid Sequence. Given an integer $n$, we want to construct a sequence of size $2n-1$ containing integers from $1$ to $n$ where $1$ occurs once and other numbers occur twice (spaced exactly by their value).

Greedy Backtracking Strategy

To find the lexicographically largest sequence, we should try to place the largest possible numbers at the earliest indexes. Therefore, we use backtracking and attempt to place numbers from $n$ down to $1$ at each vacant index:

• For $num > 1$, we must place it at index i and index i + num.
• For $num = 1$, we place it at index i.

TypeScript Implementation

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; // Filled the array successfully
        if (result[index] !== 0) return backtrack(index + 1); // Skip already filled slots
        
        for (let num = n; num >= 1; num--) { // Try placing largest number first
            if (used[num]) continue;
            
            if (num === 1) {
                result[index] = 1;
                used[1] = true;
                if (backtrack(index + 1)) return true;
                used[1] = false;
                result[index] = 0;
            } else {
                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;
}

Complexity

• Time Complexity: $O(N!)$ worst case due to backtracking permutations. However, because we search greedily from largest to smallest, the target sequence is found very early.
• Space Complexity: $O(N)$ to store the sequence array, the recursion stack, and tracking arrays.