Construct The Lexicographically Largest Valid Sequence - Leetcode Solution

Problem statement:

Given an integer n, find a sequence that satisfies all of the following constraints:

1. The integer 1 occurs once in the sequence.
2. Each integer between 2 and n occurs twice in the sequence.
3. For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.
4. The sequence is lexicographically largest.

Return the lexicographically largest valid sequence. It is guaranteed that under the given constraints, there is always a valid sequence.

Solution:

To construct the lexicographically largest valid sequence, we can start with the largest numbers and work our way down. We can start with the largest number n and place it in the first position. Then, we can place the next largest number n-1 in the position that is i+d, where i is the current position and d is the distance required by the problem (which is i itself). Then we can place n-2 in the next position, and so on. In this way, we can construct a valid sequence that is also lexicographically largest.

Here is a step-by-step algorithm to solve this problem:

1. Create an empty result array of size 2n-1.
2. Initialize the first element of the result array to 1.
3. Initialize two pointers l and r to 0 and 1 respectively.
4. For each number i from n to 2, do the following: a. If i is even, set result[r+i-1] = i, result[l+i-1] = i-1. b. If i is odd, set result[r+i-1] = i-1, result[l+i-1] = i. c. Increment l by i-1 and r by i.
5. Return the result array.

Explanation:

We start with the number n and place it in the first position (i.e., result[0] = n). Then, we need to place the number n-1 at a distance of 2 from the current position. Since the distance required is i itself (i.e., 2), we can place n-1 at index 1, which is i-1 away from the current position. Similarly, we can place n-2 at a distance of 3 from the current position, n-3 at a distance of 4, and so on. We keep track of two pointers l and r, which represent the left and right ends of the current sequence. By incrementing l by i-1 and r by i, we are ensuring that the next pair of values (i.e., i-1 and i) are placed at the required distance from each other.

For example, let's say n=5. We start with the first element as 5 (i.e., result[0]=5). Then, we need to place 4 and 3 at a distance of 2 and 3 respectively from the first element. Therefore, we can place 4 at index 1 (i.e., result[1]=4) and 3 at index 4 (i.e., result[4]=3). Similarly, we can place 2 and 1 at indices 2 and 6 respectively.

The resulting array would be [5,4,2,3,1,4,5], which satisfies all the constraints of the problem and is also the lexicographically largest sequence possible.

Time Complexity:

The time complexity of the above algorithm is O(n), since we are iterating over all numbers from n to 2 and performing constant time operations inside the loop. Therefore, the algorithm is efficient and can handle large values of n without any issues.

1