Watch 10 video solutions for Construct the Lexicographically Largest Valid Sequence, a medium level problem involving Array, Backtracking. This walkthrough by NeetCodeIO has 11,700 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer n, find a sequence that satisfies all of the following:
1 occurs once in the sequence.2 and n occurs twice in the sequence.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