Construct the Lexicographically Largest Valid Sequence

Problem

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.

Examples

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

Solution

Method 1 - Backtracking

The problem asks for constructing a sequence meeting the described conditions. The sequence must satisfy three major constraints, and we must also make it lexicographically largest. Here's the reasoning:

Approach

Backtracking and Placement Strategy:
- Start with an empty array of size (2 * n - 1) since:
  - 1 occurs once.
  - All integers 2 to n occur twice.
  - Between the two occurrences of i, their distance is exactly i, so the sequence length is determined by 2n - 1.
- Place n first to maximise the sequence lexicographically, then place n-1, and so on until 1.
Constraints Check:
- For each i where 2 <= i <= n, ensure the two indices where i is placed have a difference of i exactly. Place 1 wherever feasible since it occurs only once.
Backtracking:
- Try placing each number from highest (n) to lowest (1).
- If a number cannot be placed (due to overlaps or constraint violations), backtrack and try alternative placements.
Base Case:
- If all numbers are placed correctly, return the sequence.
Lexicographical Order:
- By placing larger numbers first (n → 1), the sequence will naturally be lexicographically largest.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java

class Solution {
    // Declare private properties for the class
    private int[] ans;      // The result array
    private boolean[] used; // To track which numbers are placed
    private int n;          // Maximum number

    public int[] constructDistancedSequence(int n) {
        // Initialize class properties
        this.n = n;
        int size = 2 * n - 1;
        this.ans = new int[size];
        this.used = new boolean[n + 1];

        // Begin backtracking from position 0
        placeNumbers(0);

        // Return the final constructed sequence
        return ans;
    }

    private boolean placeNumbers(int pos) {
        // Base case: if all positions are filled, return true
        if (pos == ans.length) {
            // Check if all numbers are placed
            for (int i = 1; i <= n; i++) {
                if (!used[i]) {
	                return false;
                }
            }
            return true;
        }

        // Skip already filled positions
        if (ans[pos] != 0) {
            return placeNumbers(pos + 1);
        }

        // Try placing numbers, starting from n to 1 for lexicographical order
        for (int num = n; num >= 1; num--) {
            if (!used[num]) {
                if (num == 1) {
                    // Special case: Place '1' at pos as it occurs only once
                    ans[pos] = 1;
                    used[1] = true;

                    if (placeNumbers(pos + 1)) {
	                    return true;
	                }

                    // Backtracking
                    ans[pos] = 0;
                    used[1] = false;
                } else if (pos + num < ans.length && ans[pos] == 0 && ans[pos + num] == 0) {
                    // Place 'num' at pos and pos + num, ensuring the proper distance
                    ans[pos] = num;
                    ans[pos + num] = num;
                    used[num] = true;

                    if (placeNumbers(pos + 1)) {
	                    return true;
	                }

                    // Backtracking: undo the placement
                    ans[pos] = 0;
                    ans[pos + num] = 0;
                    used[num] = false;
                }
            }
        }

        // If no valid placement is possible, return false
        return false;
    }
}

Python

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        size = 2 * n - 1
        ans = [0] * size
        used = [False] * (n + 1)
        
        def backtrack(pos: int) -> bool:
            if pos == size:
                return all(used[1:])  # Ensure all numbers from 1 to n were used
            
            if ans[pos] != 0:
                return backtrack(pos + 1)  # Skip already filled position
            
            for num in range(n, 0, -1):  # Start from largest num to make the sequence lexicographically largest
                if used[num]:
                    continue
                
                # Try to place 'num' at `pos` and `pos + num` if num > 1
                if num == 1:
                    ans[pos] = 1
                    used[1] = True
                    if backtrack(pos + 1):
                        return True
                    ans[pos] = 0
                    used[1] = False
                
                elif pos + num < size and ans[pos] == 0 and ans[pos + num] == 0:
                    ans[pos], ans[pos + num] = num, num
                    used[num] = True
                    if backtrack(pos + 1):
                        return True
                    # Backtracking
                    ans[pos], ans[pos + num] = 0, 0
                    used[num] = False
            
            return False  # No valid placement was made

        backtrack(0)
        return ans

Complexity

⏰ Time complexity: O(n!)
- The complexity arises from the recursive backtracking. In the worst case, the solution will explore multiple placements but has a clear upper bound since the sequence is fixed in length.
- O(n!) in the extreme worst case due to the factorial nature of placements, but optimised heavily by constraints and pruning.
🧺 Space complexity: O(n), where n is the recursion stack at peak (containing numbers to be placed in the sequence).