Construct the Lexicographically Largest Valid Sequence

Med

#1574Time: 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`.

Patterns

Backtracking

Data structures

Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    List<int[]> solutions;7    boolean[] used;8    int n;9    int[] currentSequence;10 11    public int[] constructDistancedSequence(int n) {12        this.n = n;13        this.solutions = new ArrayList<>();14        this.used = new boolean[n + 1];15        this.currentSequence = new int[2 * n - 1];16        17        generateAll(0);18        19        // This part is inefficient as it requires finding all solutions first.20        if (solutions.isEmpty()) return new int[0];21 22        int[] largest = solutions.get(0);23        for (int i = 1; i < solutions.size(); i++) {24            if (isLexicographicallyLarger(solutions.get(i), largest)) {25                largest = solutions.get(i);26            }27        }28        return largest;29    }30 31    private void generateAll(int index) {32        if (index == currentSequence.length) {33            solutions.add(Arrays.copyOf(currentSequence, currentSequence.length));34            return;35        }36 37        if (currentSequence[index] != 0) {38            generateAll(index + 1);39            return;40        }41 42        // Iterate through numbers in an arbitrary order (e.g., 1 to n)43        for (int i = 1; i <= n; i++) {44            if (used[i]) continue;45 46            currentSequence[index] = i;47            used[i] = true;48 49            if (i == 1) {50                generateAll(index + 1);51            } else {52                int secondPos = index + i;53                if (secondPos < currentSequence.length && currentSequence[secondPos] == 0) {54                    currentSequence[secondPos] = i;55                    generateAll(index + 1);56                    currentSequence[secondPos] = 0; // Backtrack57                }58            }59            60            currentSequence[index] = 0; // Backtrack61            used[i] = false;62        }63    }64    65    private boolean isLexicographicallyLarger(int[] a, int[] b) {66        for (int i = 0; i < a.length; i++) {67            if (a[i] > b[i]) return true;68            if (a[i] < b[i]) return false;69        }70        return false;71    }72}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    int[] result;3    boolean[] used;4    int n;5 6    public int[] constructDistancedSequence(int n) {7        this.n = n;8        result = new int[2 * n - 1];9        used = new boolean[n + 1];10        solve(0);11        return result;12    }13 14    private boolean solve(int index) {15        // Base case: we have successfully filled the entire sequence16        if (index == result.length) {17            return true;18        }19 20        // If the current position is already filled, move to the next one21        if (result[index] != 0) {22            return solve(index + 1);23        }24 25        // Iterate from the largest number down to 1 to ensure lexicographically largest26        for (int i = n; i >= 1; i--) {27            // If the number has already been used, skip it28            if (used[i]) {29                continue;30            }31 32            // Try to place i33            result[index] = i;34            used[i] = true;35 36            if (i == 1) {37                // If 1 is placed, recurse. If it leads to a solution, we are done.38                if (solve(index + 1)) {39                    return true;40                }41            } else {42                // For i > 1, check and place the second occurrence43                int secondPos = index + i;44                if (secondPos < result.length && result[secondPos] == 0) {45                    result[secondPos] = i;46                    // Recurse. If it leads to a solution, we are done.47                    if (solve(index + 1)) {48                        return true;49                    }50                    // Backtrack the second occurrence51                    result[secondPos] = 0;52                }53            }54 55            // Backtrack the first occurrence and the used flag56            result[index] = 0;57            used[i] = false;58        }59 60        // If no number can be placed at this index, this path is invalid61        return false;62    }63}

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int[] path;4private5  int[] cnt;6private7  int n;8public9  int[] constructDistancedSequence(int n) {10    this.n = n;11    path = new int[n * 2];12    cnt = new int[n * 2];13    Arrays.fill(cnt, 2);14    cnt[1] = 1;15    dfs(1);16    int[] ans = new int[n * 2 - 1];17    for (int i = 0; i < ans.length; ++i) {18      ans[i] = path[i + 1];19    }20    return ans;21  }22private23  boolean dfs(int u) {24    if (u == n * 2) {25      return true;26    }27    if (path[u] > 0) {28      return dfs(u + 1);29    }30    for (int i = n; i > 1; --i) {31      if (cnt[i] > 0 && u + i < n * 2 && path[u + i] == 0) {32        cnt[i] = 0;33        path[u] = i;34        path[u + i] = i;35        if (dfs(u + 1)) {36          return true;37        }38        cnt[i] = 2;39        path[u] = 0;40        path[u + i] = 0;41      }42    }43    if (cnt[1] > 0) {44      path[u] = 1;45      cnt[1] = 0;46      if (dfs(u + 1)) {47        return true;48      }49      cnt[1] = 1;50      path[u] = 0;51    }52    return false;53  }54}

1class Solution {2public:3  int n;4  vector<int> cnt, path;5  vector<int> constructDistancedSequence(int _n) {6    n = _n;7    cnt.resize(n * 2, 2);8    path.resize(n * 2);9    cnt[1] = 1;10    dfs(1);11    vector<int> ans;12    for (int i = 1; i < n * 2; ++i)13      ans.push_back(path[i]);14    return ans;15  }16  bool dfs(int u) {17    if (u == n * 2)18      return 1;19    if (path[u])20      return dfs(u + 1);21    for (int i = n; i > 1; --i) {22      if (cnt[i] && u + i < n * 2 && !path[u + i]) {23        path[u] = path[u + i] = i;24        cnt[i] = 0;25        if (dfs(u + 1))26          return 1;27        cnt[i] = 2;28        path[u] = path[u + i] = 0;29      }30    }31    if (cnt[1]) {32      path[u] = 1;33      cnt[1] = 0;34      if (dfs(u + 1))35        return 1;36      cnt[1] = 1;37      path[u] = 0;38    }39    return 0;40  }41};

1class Solution:2    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:]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem