1718. Construct the Lexicographically Largest Valid Sequence

Problem

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 (Java)

class Solution {
    public int[] constructDistancedSequence(int n) {
        int[] result = new int[n * 2 - 1];
        boolean[] visited = new boolean[n + 1];
        backtracking(0, result, visited, n);
        return result;
    }

    private boolean backtracking(int index, int[] result, boolean[] visited, int n) {
        if (index == result.length) {
            return true;
        }
        if (result[index] != 0) {
            return backtracking(index + 1, result, visited, n);
        } else {
            for (int i = n; i > 0; i--) {
                if (visited[i]) {
                    continue;
                }
                visited[i] = true;
                result[index] = i;
                if (i == 1) {
                    if (backtracking(index + 1, result, visited, n)) {
                        return true;
                    }
                } else if (index + i < result.length && result[index + i] == 0) {
                    result[i + index] = i;
                    if (backtracking(index + 1, result, visited, n)) {
                        return true;
                    }
                    result[index + i] = 0;
                }
                result[index] = 0;
                visited[i] = false;
            }
        }
        return false;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).