{x}
blog image

Construct the Lexicographically Largest Valid Sequence

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.

 

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 Explanation:

This problem asks to construct the lexicographically largest valid sequence given an integer n. The sequence must satisfy three conditions: 1 appears once, integers from 2 to n appear twice, and the distance between the two occurrences of each integer i (2 to n) is exactly i.

The solution uses a backtracking approach. Backtracking is suitable because we explore different possibilities, and if a path doesn't lead to a valid solution, we backtrack to try another path.

Approach:

  1. Data Structures:

    • path: An array to store the constructed sequence. It's initialized with zeros. The size is 2n because each number (except 1) appears twice.
    • cnt: An array to keep track of the count of each number. Initially, cnt[i] = 2 for 2 ≤ i ≤ n and cnt[1] = 1. As we place numbers in the path, we decrement their counts in cnt.

  2. Depth-First Search (DFS): The core of the solution is a recursive DFS function.

    • Base Case: If we've filled the entire path (reached the end of the sequence), it means we found a valid sequence, so we return true.

    • Recursive Step: If path[u] is already filled, we skip it and recursively call dfs(u+1). Otherwise, we try to fill path[u] with numbers from n down to 1.

      • For numbers 2 to n: We check if the count cnt[i] is greater than 0 and if placing i at u allows us to place another i at u + i without going out of bounds, and if the position u+i is empty (path[u+i] == 0). If all conditions are met, we place i at both positions (path[u] and path[u+i]), decrement cnt[i], and recursively call dfs(u+1). If the recursive call is successful, we return true; otherwise, we backtrack by resetting path[u] and path[u+i] to 0 and restoring cnt[i].

      • For number 1: We handle 1 separately because it appears only once. We check if cnt[1] is greater than 0 and place 1 at path[u]. Then, we make a recursive call. If successful, we return true; otherwise, we backtrack.

  3. Lexicographically Largest: The algorithm inherently finds the lexicographically largest sequence because it tries larger numbers first (in the loop for i in range(n, 1, -1)).

Time and Space Complexity:

  • Time Complexity: O(n!), where n is the input integer. In the worst case, the DFS explores all possible permutations of the numbers, leading to a factorial time complexity. However, due to the constraints (n ≤ 20), it remains computationally feasible.

  • Space Complexity: O(n). The space is primarily used by the path and cnt arrays, which have a size proportional to n. The recursive calls of the DFS also consume stack space, which is also proportional to n in the worst case.

Code Explanation (Python):

The Python code directly implements the approach described above. The dfs function performs the backtracking search, and the main part of the code initializes the data structures and calls dfs. The result is returned after removing the first element (index 0) from path because we start the search at index 1. The rest of the code implementations in Java, C++, and Go follow a similar structure, adapting to their respective syntax and features.