# Construct the Lexicographically Largest Valid Sequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence)
Canonical: https://scaleengineer.com/dsa/problems/construct-the-lexicographically-largest-valid-sequence
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
---
## Problem
Given an integer `n`, find a sequence with elements in the range `[1, n]` 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`

# Approaches
## Brute-Force Backtracking (Generate All Sequences)
This approach involves finding every possible valid sequence that satisfies the given conditions. We use a standard backtracking algorithm to explore all placement possibilities. After generating all valid sequences, we compare them to find the one that is lexicographically the largest.
**Time:** O(S * n * n!), where S is the number of valid sequences. The algorithm explores a very large search space to find all solutions, making it very slow for larger `n`. · **Space:** O(S * n), where S is the number of valid sequences. This is because we need to store all S solutions, each of length `2n - 1`.
**Pros:** It is a conceptually simple application of backtracking that guarantees finding the correct answer.
**Cons:** Extremely inefficient in terms of time complexity as it explores the entire search space for all possible valid sequences.; Requires a large amount of memory to store all the generated sequences, leading to poor space complexity.
### Explanation
The fundamental idea is to treat this as a permutation problem with constraints. We can build a sequence recursively. A helper function, say `generateAll(index)`, attempts to fill the sequence from the given `index`. It tries placing each unused number `i` (from 1 to n) at the current position and, if `i > 1`, its corresponding pair at `index + i`. If a placement is valid, it recurses to the next position. When a full valid sequence is formed, it's stored in a list. This process continues until all possibilities are exhausted. Finally, the list of solutions is scanned to find the lexicographically greatest sequence.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    List<int[]> solutions;
    boolean[] used;
    int n;
    int[] currentSequence;

    public int[] constructDistancedSequence(int n) {
        this.n = n;
        this.solutions = new ArrayList<>();
        this.used = new boolean[n + 1];
        this.currentSequence = new int[2 * n - 1];
        
        generateAll(0);
        
        // This part is inefficient as it requires finding all solutions first.
        if (solutions.isEmpty()) return new int[0];

        int[] largest = solutions.get(0);
        for (int i = 1; i < solutions.size(); i++) {
            if (isLexicographicallyLarger(solutions.get(i), largest)) {
                largest = solutions.get(i);
            }
        }
        return largest;
    }

    private void generateAll(int index) {
        if (index == currentSequence.length) {
            solutions.add(Arrays.copyOf(currentSequence, currentSequence.length));
            return;
        }

        if (currentSequence[index] != 0) {
            generateAll(index + 1);
            return;
        }

        // Iterate through numbers in an arbitrary order (e.g., 1 to n)
        for (int i = 1; i <= n; i++) {
            if (used[i]) continue;

            currentSequence[index] = i;
            used[i] = true;

            if (i == 1) {
                generateAll(index + 1);
            } else {
                int secondPos = index + i;
                if (secondPos < currentSequence.length && currentSequence[secondPos] == 0) {
                    currentSequence[secondPos] = i;
                    generateAll(index + 1);
                    currentSequence[secondPos] = 0; // Backtrack
                }
            }
            
            currentSequence[index] = 0; // Backtrack
            used[i] = false;
        }
    }
    
    private boolean isLexicographicallyLarger(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] > b[i]) return true;
            if (a[i] < b[i]) return false;
        }
        return false;
    }
}
```
### Algorithm
- Create a recursive backtracking function, say `generateAll(index)`, to build the sequence.
- Use a boolean array `used` to keep track of numbers from `1` to `n` that have been placed in the sequence.
- The recursive function will try to fill a `sequence` array of size `2n - 1`.
- **Base Case:** If the `index` reaches the end of the sequence (`2n - 1`), a valid sequence has been found. Add a copy of it to a list of solutions.
- **Recursive Step:**
  - If the current position `sequence[index]` is already filled, recurse on the next index: `generateAll(index + 1)`.
  - Otherwise, iterate through numbers `i` from `1` to `n`.
  - For each `i` that has not been used:
    - Try to place `i` at `sequence[index]`. If `i > 1`, its second occurrence must be placed at `index + i`.
    - If the placement is valid (i.e., the second position is within bounds and is empty), mark `i` as used, update the sequence, and make a recursive call: `generateAll(index + 1)`.
    - After the recursive call returns, backtrack by undoing the placement and unmarking `i` as used.
- After the initial call `generateAll(0)` completes, iterate through the list of all found solutions to find and return the lexicographically largest one.

## Optimized Backtracking with Greedy Search
This approach improves upon the brute-force method by integrating the "lexicographically largest" requirement directly into the search process. By making greedy choices (placing the largest available numbers at the earliest possible positions), we ensure that the very first valid sequence we find is the one we're looking for. This allows us to stop the search immediately, avoiding the generation of all other solutions.
**Time:** O(n!). While the theoretical worst-case is exponential, this approach is very fast in practice because the search space is heavily pruned by the constraints and the greedy strategy. The search stops as soon as the first (and largest) solution is found. · **Space:** O(n) for storing the result array, the `used` boolean array, and the recursion stack depth, which is at most `2n - 1`.
**Pros:** Highly efficient as it finds the optimal solution directly and terminates early.; Optimal space complexity, using only O(n) space for the result, visited array, and recursion stack.; Guaranteed to find the lexicographically largest sequence due to the greedy search order.
**Cons:** The recursive nature of backtracking can be hard to reason about for beginners.; While efficient for the given constraints, the time complexity is still exponential in the worst case.
### Explanation
To find the lexicographically largest sequence, we should try to place larger numbers at earlier indices. This suggests a greedy approach combined with backtracking. We build the sequence from left to right (from index 0). At each empty position, we try to place the largest possible number (from `n` down to `1`) that hasn't been used yet and satisfies the distance constraint.

We use a recursive function that returns a boolean indicating whether a solution was found. The first time a complete sequence is formed, we know it must be the lexicographically largest because of our greedy, descending-order search for numbers to place. We can then stop the entire search process.

```java
class Solution {
    int[] result;
    boolean[] used;
    int n;

    public int[] constructDistancedSequence(int n) {
        this.n = n;
        result = new int[2 * n - 1];
        used = new boolean[n + 1];
        solve(0);
        return result;
    }

    private boolean solve(int index) {
        // Base case: we have successfully filled the entire sequence
        if (index == result.length) {
            return true;
        }

        // If the current position is already filled, move to the next one
        if (result[index] != 0) {
            return solve(index + 1);
        }

        // Iterate from the largest number down to 1 to ensure lexicographically largest
        for (int i = n; i >= 1; i--) {
            // If the number has already been used, skip it
            if (used[i]) {
                continue;
            }

            // Try to place i
            result[index] = i;
            used[i] = true;

            if (i == 1) {
                // If 1 is placed, recurse. If it leads to a solution, we are done.
                if (solve(index + 1)) {
                    return true;
                }
            } else {
                // For i > 1, check and place the second occurrence
                int secondPos = index + i;
                if (secondPos < result.length && result[secondPos] == 0) {
                    result[secondPos] = i;
                    // Recurse. If it leads to a solution, we are done.
                    if (solve(index + 1)) {
                        return true;
                    }
                    // Backtrack the second occurrence
                    result[secondPos] = 0;
                }
            }

            // Backtrack the first occurrence and the used flag
            result[index] = 0;
            used[i] = false;
        }

        // If no number can be placed at this index, this path is invalid
        return false;
    }
}
```
### Algorithm
- The core of the algorithm is a recursive function, `solve(index)`, that attempts to fill a `result` array of size `2n - 1`.
- A boolean array `used` of size `n + 1` tracks which numbers have been placed.
- The function returns `true` upon finding the first valid sequence, and `false` otherwise.
- **Base Case:** If `index` reaches the end of the `result` array, a full sequence has been constructed. Return `true` to signal success.
- **Recursive Step:**
  - If `result[index]` is already filled (by a previous placement of a pair), skip to the next position by calling `solve(index + 1)`.
  - If `result[index]` is empty, iterate through numbers `i` in **descending order** from `n` down to `1`.
  - For each number `i` that has not been used:
    - Place `i` at `result[index]` and mark it as used.
    - If `i > 1`, place its second occurrence at `result[index + i]`. This is only done if `index + i` is a valid and empty position.
    - Make a recursive call: `solve(index + 1)`.
    - If the recursive call returns `true`, it means a solution was found. We immediately return `true` to stop the search.
    - If the call returns `false`, backtrack: undo the placement in `result` and `used`, and continue the loop to try the next smaller number.
- If the loop completes without finding a valid placement, return `false`.
- The initial call is `solve(0)`. Since we always try the largest numbers first, the first solution found is guaranteed to be the lexicographically largest.

# Solutions
### Java

```java
class Solution {
private
  int[] path;
private
  int[] cnt;
private
  int n;
public
  int[] constructDistancedSequence(int n) {
    this.n = n;
    path = new int[n * 2];
    cnt = new int[n * 2];
    Arrays.fill(cnt, 2);
    cnt[1] = 1;
    dfs(1);
    int[] ans = new int[n * 2 - 1];
    for (int i = 0; i < ans.length; ++i) {
      ans[i] = path[i + 1];
    }
    return ans;
  }
private
  boolean dfs(int u) {
    if (u == n * 2) {
      return true;
    }
    if (path[u] > 0) {
      return dfs(u + 1);
    }
    for (int i = n; i > 1; --i) {
      if (cnt[i] > 0 && u + i < n * 2 && path[u + i] == 0) {
        cnt[i] = 0;
        path[u] = i;
        path[u + i] = i;
        if (dfs(u + 1)) {
          return true;
        }
        cnt[i] = 2;
        path[u] = 0;
        path[u + i] = 0;
      }
    }
    if (cnt[1] > 0) {
      path[u] = 1;
      cnt[1] = 0;
      if (dfs(u + 1)) {
        return true;
      }
      cnt[1] = 1;
      path[u] = 0;
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int n;
  vector<int> cnt, path;
  vector<int> constructDistancedSequence(int _n) {
    n = _n;
    cnt.resize(n * 2, 2);
    path.resize(n * 2);
    cnt[1] = 1;
    dfs(1);
    vector<int> ans;
    for (int i = 1; i < n * 2; ++i)
      ans.push_back(path[i]);
    return ans;
  }
  bool dfs(int u) {
    if (u == n * 2)
      return 1;
    if (path[u])
      return dfs(u + 1);
    for (int i = n; i > 1; --i) {
      if (cnt[i] && u + i < n * 2 && !path[u + i]) {
        path[u] = path[u + i] = i;
        cnt[i] = 0;
        if (dfs(u + 1))
          return 1;
        cnt[i] = 2;
        path[u] = path[u + i] = 0;
      }
    }
    if (cnt[1]) {
      path[u] = 1;
      cnt[1] = 0;
      if (dfs(u + 1))
        return 1;
      cnt[1] = 1;
      path[u] = 0;
    }
    return 0;
  }
};

```

### Python

```python
class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]: def dfs(u): if u == n * 2: return True if path[u]: return dfs(u + 1) for i in range(n, 1, - 1): if cnt[i] and u + i < n * 2 and path[u + i] == 0: cnt[i] = 0 path[u] = path[u + i] = i if dfs(u + 1): return True path[u] = path[u + i] = 0 cnt[i] = 2 if cnt[1]: cnt[1], path[u] = 0, 1 if dfs(u + 1): return True path[u], cnt[1] = 0, 1 return False path = [0] * (n * 2) cnt = [2] * (n * 2) cnt[1] = 1 dfs(1) return path[1:]

```