Construct the Lexicographically Largest Valid Sequence

Construct the Lexicographically Largest Valid Sequence - Problem

Array Backtracking Medium

Given an integer n, find a sequence with elements in the range [1, n] that satisfies all of the following conditions:

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.

Input & Output

Example 1 — Small Case

$ Input: n = 3

› Output: [3,1,2,3,2]

💡 Note: For n=3, we need sequence with 1 once, 2 twice, 3 twice. Distance between two 2's is |3-1|=2 ✓, distance between two 3's is |4-0|=4≠3 ✗. Correct answer: [3,1,2,3,2] where 2's are at positions 2,4 (distance 2) and 3's are at positions 0,3 (distance 3).

Example 2 — Minimum Case

$ Input: n = 1

› Output: [1]

💡 Note: For n=1, only need number 1 once. The sequence is simply [1].

Example 3 — Medium Case

$ Input: n = 4

› Output: [4,1,3,1,2,4,2]

💡 Note: For n=4: 1 occurs once, 2,3,4 occur twice each. All distance constraints satisfied: 2's at distance 2, 3's at distance 3, 4's at distance 4. This is the lexicographically largest valid sequence.

Constraints

1 ≤ n ≤ 20

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=3, need sequence with specific distance rules

Requirements

1 appears once, 2 and 3 appear twice each, with distance constraints

Output

Lexicographically largest valid sequence [3,1,2,3,2]

Key Takeaway

🎯 Key Insight: Use backtracking with greedy placement (try larger numbers first) to build the lexicographically largest sequence while satisfying distance constraints

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is to use backtracking with greedy placement - try larger numbers first at each position to ensure lexicographically largest result. Best approach is backtracking with constraint checking. Time: O(n!), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Greedy Placement	O(n!)	O(n)	Use backtracking to place numbers greedily, trying larger numbers first for lexicographically largest result
Brute Force - Generate All Permutations	O((2n)!)	O(2n)	Generate all possible sequences and check which ones satisfy constraints

Backtracking with Greedy Placement — Algorithm Steps

Initialize empty sequence of length 2n-1
For each position, try placing numbers from n down to 1
Check if placement satisfies distance constraints
Recursively fill remaining positions
Backtrack if no valid placement found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Empty

Initialize sequence [0,0,0,0,0] for n=3

Try Largest First

At each position, try 3, then 2, then 1

Check Constraints

Verify distance rules before placing

Backtrack

Remove and try next number if constraints fail

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(int* sequence, bool* used, int pos, int n, int length) {
    if (pos == length) {
        return true;
    }
    
    if (sequence[pos] != 0) {  // Position already filled
        return backtrack(sequence, used, pos + 1, n, length);
    }
    
    // Try numbers from n down to 1 for lexicographically largest
    for (int num = n; num >= 1; num--) {
        if (used[num]) {
            continue;
        }
        
        if (num == 1) {
            // Place 1 at current position
            sequence[pos] = 1;
            used[1] = true;
            if (backtrack(sequence, used, pos + 1, n, length)) {
                return true;
            }
            sequence[pos] = 0;
            used[1] = false;
        } else {
            // Try to place num at current position and num positions later
            if (pos + num < length && sequence[pos + num] == 0) {
                sequence[pos] = num;
                sequence[pos + num] = num;
                used[num] = true;
                if (backtrack(sequence, used, pos + 1, n, length)) {
                    return true;
                }
                sequence[pos] = 0;
                sequence[pos + num] = 0;
                used[num] = false;
            }
        }
    }
    
    return false;
}

int* solution(int n) {
    int length = 2 * n - 1;
    int* sequence = (int*)calloc(length, sizeof(int));
    bool* used = (bool*)calloc(n + 1, sizeof(bool));
    
    backtrack(sequence, used, 0, n, length);
    
    free(used);
    return sequence;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int* result = solution(n);
    int length = 2 * n - 1;
    
    printf("[");
    for (int i = 0; i < length; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Backtracking with pruning, but worst case still factorial due to trying all valid placements

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and sequence storage

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Greedy Placement — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler