Construct The Lexicographically Largest Valid Sequence · Interview Problem

Leetcode

Medium

Arrays

Backtracking

Greedy

Google

Problem

Given an integer $n$ , build an array seq of length 2n - 1 using every integer from 1 to n subject to these rules:

The number 1 appears exactly once.
Each number x where 2 <= x <= n appears exactly twice.
For every x >= 2, the two occurrences of x must be exactly x indices apart.
- If the first occurrence is at index i, the second must be at index i + x.

Among all valid arrays, return the lexicographically largest one.

A valid sequence is guaranteed to exist for the intended input range.

Input Format

A single integer n.
Construct an array of length 2n - 1 satisfying the rules above.

Output Format

Return the lexicographically largest valid sequence as an integer array.

Constraints

$1 \le n$
The sequence length is $2n - 1$
For each $x \in [2, n]$ , there must be exactly two occurrences separated by $x$ positions
The value 1 appears exactly once
A valid construction exists

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 3

Output

[3,1,2,3,2]

Explanation

The sequence has length 5. 3 appears at indices 0 and 3, and 2 appears at indices 2 and 4. 1 appears once. This is the lexicographically largest valid sequence for n = 3.

Example 2

Input

n = 5

Output

[5,3,1,4,3,5,2,4,2]

Explanation

All numbers from 1 to 5 are used correctly. The two 5s are 5 apart, the two 4s are 4 apart, the two 3s are 3 apart, and the two 2s are 2 apart.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress