Construct the Lexicographically Largest Valid Sequence - Solution & Explanation
Problem Statement
Given an integer n, find a sequence that satisfies all of the following:
- The integer
1occurs once in the sequence. - Each integer between
2andnoccurs twice in the sequence. - For every integer
ibetween2andn, the distance between the two occurrences ofiis exactlyi.
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
Approach Overview
Problem Overview: You need to build an array of length 2n - 1 using numbers from 1 to n. Each number k > 1 must appear exactly twice and the distance between the two occurrences must be k. Number 1 appears once. Among all valid sequences, return the lexicographically largest one.
Approach 1: Backtracking with Greedy Placement (Time: O(n!), Space: O(n))
This is the most common solution and the one typically expected in interviews. Use backtracking to fill the sequence from left to right. At each empty index, try placing numbers from n down to 1. For values greater than 1, you must check whether index i + k is within bounds and also empty before placing both occurrences. Mark the number as used, continue recursion, and revert the placement if it leads to a dead end. Trying larger numbers first guarantees the first valid sequence you find is already the lexicographically largest. The search space is exponential, but pruning invalid placements early keeps it manageable.
Approach 2: Iterative Construction (Time: O(n^2), Space: O(n))
An iterative strategy builds the sequence while scanning the array and attempting placements based on available numbers. Maintain a result array and a structure that tracks which numbers are still unused. When encountering an empty position, try inserting the largest remaining number that satisfies the distance constraint. This approach relies on repeated checks and adjustments as the sequence grows. It works well for moderate n values and avoids recursion overhead, though it still performs many placement validations.
Approach 3: Divide and Conquer Placement (Time: O(n!), Space: O(n))
You can model the problem as recursively solving subsegments of the array. Pick the largest unused number and attempt to place it at valid positions within the current segment. Once placed, the array splits into smaller independent segments that must also satisfy the same constraints. The recursive structure resembles divide-and-conquer: each placement reduces the problem size and creates smaller subproblems. In practice this behaves similarly to backtracking but conceptually emphasizes segment decomposition within the array.
Approach 4: Heap-based Ordering (Time: O(n log n), Space: O(n))
A heap can help prioritize which numbers to attempt first. Store unused numbers in a max-heap so the largest value is always considered before smaller ones. While scanning the sequence, extract the largest candidate and check if its required distance placement is valid. If placement fails, temporarily skip it and reinsert it later. The heap guarantees lexicographic preference toward larger numbers while maintaining efficient retrieval.
Recommended for interviews: The backtracking solution is the expected answer. Interviewers want to see how you model constraints, prune invalid states, and enforce lexicographic ordering by trying larger numbers first. Starting with brute-force placement shows understanding, but implementing efficient backtracking with early validation demonstrates strong problem-solving skills.
Approach 1: Backtracking Solution
This approach involves using a backtracking method to build the sequence from the largest number down to the smallest. We place numbers starting from n and try placing each number in positions that satisfy the distance requirement. If we find a valid placement for a given number, we continue to place the next smaller number. When all numbers are placed correctly, we have a solution. The constraint n ≤ 20 makes this approach feasible.
This Python solution uses a recursive backtracking approach to fill in the sequence from the largest number down to 1. The array `result` is used to store the current sequence configuration, and `used` keeps track of which numbers have been placed. The `backtrack` function attempts to place each number in allowed positions and recurses until a solution is found.
Code
Python
Complexity
Time Complexity: O(n!) due to the combinatorial nature of backtracking.
Space Complexity: O(n) for the result and used arrays.
Approach 2: Iterative Construction
This approach constructs the sequence iteratively. It tries to place numbers from n down to 2 at allowed positions while ensuring the distance constraint is met. The challenge is to ensure placement satisfies both the distance and the need for the largest lexicographical order. The placement involves checking possible slots and filling iteratively.
This C++ solution iteratively places numbers from n to 2 with a main loop that attempts to place each number in its valid slots by checking indices. The innermost loop ensures that upon finding a valid slot, the number is placed, and iteration continues. Finally, the number 1 is placed in the first open slot.
Code
C++
Complexity
Time Complexity: O(n^2) due to two nested loops traversing the positions.
Space Complexity: O(n) for storing the result sequence.
Approach 3: Approach 1: Using Divide and Conquer
This approach breaks the problem into smaller, more manageable sub-problems, solves them individually, and combines their results.
One common example is the Merge Sort, where an array is continually split in half, each half is sorted, and then merged back together.
The above C code implements merge sort. The mergeSort function recursively divides the array into two halves and sorts each side. The merge function combines the sorted halves back into a continuous array.
Complexity
Time Complexity: O(n log n) due to the divide and conquer method where each level of recursion processes half-sized arrays.
Space Complexity: O(n) for temporary arrays used in the merge process.
Approach 4: Approach 2: Using a Heap-based Sort
This approach leans on using a heap data structure to facilitate sorting. Known as Heap Sort, it involves build-heap operations and sorting through the extract-max process repeatedly.
Commonly used for its in-place sort feature with reliable time complexities.
The given C code uses a heap-based sort algorithm. It builds a max heap from the array and sorts it by moving the maximum element to the end of the array and applying heapify repeatedly.
Complexity
Time Complexity: O(n log n) due to heapify operations.
Space Complexity: O(1) as heap sort is in-place.
Approach 5: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking Solution | Time Complexity: O(n!) due to the combinatorial nature of backtracking. |
| Iterative Construction | Time Complexity: O(n^2) due to two nested loops traversing the positions. |
| Approach 1: Using Divide and Conquer | Time Complexity: O(n log n) due to the divide and conquer method where each level of recursion processes half-sized arrays. |
| Approach 2: Using a Heap-based Sort | Time Complexity: O(n log n) due to heapify operations. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Greedy Placement | O(n!) | O(n) | Best general solution. Guarantees lexicographically largest sequence and commonly expected in interviews. |
| Iterative Construction | O(n^2) | O(n) | Useful when avoiding recursion or when implementing incremental construction logic. |
| Divide and Conquer Placement | O(n!) | O(n) | Conceptual recursive decomposition of the array into smaller segments. |
| Heap-based Ordering | O(n log n) | O(n) | When prioritizing larger numbers efficiently using a heap structure. |
Video Solution
Construct the Lexicographically Largest Valid Sequence | Detailed | Leetcode 1718 | codestorywithMIK • codestorywithMIK • 13,471 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Construct the Lexicographically Largest Valid Sequence easy or hard?
Construct the Lexicographically Largest Valid Sequence Python/Java solution
How to solve Construct the Lexicographically Largest Valid Sequence in O(n)?
What is the best approach for Construct the Lexicographically Largest Valid Sequence?
Is Construct the Lexicographically Largest Valid Sequence asked at Google/Amazon/Meta?
What data structure is used in Construct the Lexicographically Largest Valid Sequence?
What is the time complexity of Construct the Lexicographically Largest Valid Sequence?
Ready to solve this problem?
Practice Construct the Lexicographically Largest Valid Sequence with our built-in code editor and test cases.
Practice on FleetCode