Formatted question description: https://leetcode.ca/all/1718.html

1718. Construct the Lexicographically Largest Valid Sequence

Level

Medium

Description

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

• 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.

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

Solution

Use backtrack. Put the numbers into the sequence, from n to 1, starting from the current index. For each index, always try the maximum possible number so that the sequence is the lexicographically largest one.

class Solution {
    public int[] constructDistancedSequence(int n) {
        int length = n * 2 - 1;
        int[] sequence = new int[length];
        Set<Integer> visited = new HashSet<Integer>();
        backtrack(sequence, visited, 0, n, length);
        return sequence;
    }

    public boolean backtrack(int[] sequence, Set<Integer> visited, int start, int n, int length) {
        if (visited.size() == n)
            return true;
        if (sequence[start] > 0)
            return backtrack(sequence, visited, start + 1, n, length);
        for (int i = n; i > 0; i--) {
            if (!visited.contains(i)) {
                int next = start + i;
                if (i == 1 || next < length && sequence[next] == 0) {
                    sequence[start] = i;
                    if (i > 1)
                        sequence[next] = i;
                    visited.add(i);
                    if (backtrack(sequence, visited, start + 1, n, length))
                        return true;
                    sequence[start] = 0;
                    if (i > 1)
                        sequence[next] = 0;
                    visited.remove(i);
                }
            }
        }
        return false;
    }
}

All Problems

All Solutions