LeetCode 1718: Construct the Lexicographically Largest Valid Sequence Solution

Master LeetCode problem 1718 (Construct the Lexicographically Largest Valid Sequence), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1718. Construct the Lexicographically Largest Valid Sequence

Medium

Array Backtracking

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1718 (Construct the Lexicographically Largest Valid Sequence)?

This page provides optimized solutions for LeetCode problem 1718 (Construct the Lexicographically Largest Valid Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1718 (Construct the Lexicographically Largest Valid Sequence)?

The time complexity for LeetCode 1718 (Construct the Lexicographically Largest Valid Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1718 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1718 in Java, C++, or Python.

Back to LeetCode Solutions