LeetCode 1718: Construct the Lexicographically Largest Valid Sequence Solution

Problem Description

Explanation:

To construct the lexicographically largest valid sequence, we can use a backtracking approach to try all possible permutations of the numbers from 1 to n following the given constraints. We will keep track of the numbers already used and the positions of the numbers in the sequence to ensure that each integer occurs exactly twice with the required distance between occurrences.

Algorithmic Idea:

Start with an empty sequence.
For each number from n down to 1: a. If the number is not already used, try adding it to the sequence at valid positions.
Recursively explore all valid permutations until a valid sequence is found.
Return the lexicographically largest valid sequence.

Time Complexity:

The time complexity of this algorithm is O(n!) as we are trying all possible permutations.

Space Complexity:

The space complexity is O(n) for the array storing the sequence and used numbers.

Solutions

class Solution {
    public int[] constructDistancedSequence(int n) {
        int[] result = new int[2 * n - 1];
        boolean[] used = new boolean[n + 1];
        backtrack(result, used, n, 0);
        return result;
    }
    
    private boolean backtrack(int[] result, boolean[] used, int n, int pos) {
        if (pos == result.length) {
            return true;
        }
        
        if (result[pos] != 0) {
            return backtrack(result, used, n, pos + 1);
        }
        
        for (int i = n; i >= 1; i--) {
            if (used[i]) continue;
            
            if (i == 1) {
                used[i] = true;
                result[pos] = i;
                if (backtrack(result, used, n, pos + 1)) {
                    return true;
                }
                used[i] = false;
                result[pos] = 0;
            } else if (pos + i < result.length && result[pos + i] == 0) {
                used[i] = true;
                result[pos] = i;
                result[pos + i] = i;
                if (backtrack(result, used, n, pos + 1)) {
                    return true;
                }
                used[i] = false;
                result[pos] = 0;
                result[pos + i] = 0;
            }
        }
        
        return false;
    }
}