Leetcode 1718. Construct the Lexicographically Largest Valid Sequence

Jimmy   Feb 16, 2025   1226 words   ~30 mins
#Array #Backtracking

Table of Contents

Problem Informations

Problem 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 \leq n \leq 20$

Intuition

The problem demands constructing a sequence that meets the conditions of containing integers between 1 and $n$, with specific constraints on their occurrences and positions. The key challenge is to find not just any sequence but the lexicographically largest valid one. Given that each integer $i$ from $2$ to $n$ must appear twice with a specific distance of $i$, the problem inherently forms a permutation challenge. By leveraging backtracking, we can explore potential placements of each integer, ensuring that constraints are satisfied while aiming for the largest possible sequence.

Approach

The approach to solving this problem involves using backtracking. The goal is to systematically explore all possible placements of the integers from $n$ down to $1$ in a sequence array initialized to a size of $2n-1$. To detail the steps:

  1. Initialization:

    • Create a sequence array filled with -1 to represent empty positions. The size is $2n-1$, accounting for the distances required by the largest integer $n$.
    • Use a boolean array used to track whether each number from $1$ to $n$ has been placed in the sequence.

  2. Backtracking Function:

    • Start from the first index and attempt to place integers from $n$ down to $1$. Attempting numbers in descending order helps achieve a lexicographically larger sequence.
    • Skip indices that are already filled.
    • For each number, ensure that if it is not 1, there must be adequate space to place it such that the correct distance constraint is met (i.e., it can be placed at position i and i + currentNum).
    • Mark the number as used and place it in the correct positions of the sequence.
    • Recursively call the backtracking function for the next index.
    • If at any point placing a number does not lead to a complete and valid sequence, revert the changes (backtrack), and try the next possible number.

  3. Solution Verification:

    • The sequence is complete if all the positions are filled correctly when the recursion finishes.
    • If all numbers have been successfully placed with constraints satisfied, the sequence is returned.

This algorithm uses the backtracking principle efficiently by considering the constraints and trying to fulfill them in a recursive manner, always opting for the largest numbers first to ensure the lexicographic requirement.

Code

C++

class Solution {
public:
    // Backtracking function to fill the sequence
    bool backtrack(vector<int>& sequence, vector<bool>& used, int currentIndex, int n) {
        // If we've filled all required positions, the sequence is complete
        if (currentIndex >= 2 * n - 1) return true;

        // Skip already filled positions
        if (sequence[currentIndex] != -1) return backtrack(sequence, used, currentIndex + 1, n);

        // Try placing numbers from n down to 1
        for (int currentNum = n; currentNum > 0; currentNum--) {
            // Skip numbers that have already been used
            if (used[currentNum]) continue;

            // Ensure there's enough space to place the currentNum at the required distance
            if (currentNum != 1 && (currentIndex + currentNum >= 2 * n - 1 || sequence[currentIndex + currentNum] != -1)) continue;

            // Mark the current number as used
            used[currentNum] = true;

            // Place the current number in the sequence
            if (currentNum == 1) {
                sequence[currentIndex] = currentNum;
            } else {
                sequence[currentIndex] = sequence[currentIndex + currentNum] = currentNum;
            }

            // Continue the backtracking for the next index
            if (backtrack(sequence, used, currentIndex + 1, n)) return true;

            // Revert changes if placing currentNum didn't lead to a solution
            if (currentNum != 1) sequence[currentIndex + currentNum] = -1;
            used[currentNum] = false;
            sequence[currentIndex] = -1;
        }
        return false;
    }

    // Main function to construct the lexicographically largest sequence
    vector<int> constructDistancedSequence(int n) {
        // Initialize the sequence with -1 to denote empty positions
        vector<int> sequence(2 * n - 1, -1);
        
        // Initialize a boolean array to track used numbers
        vector<bool> used(n + 1, false);
        
        // Start backtracking from index 0
        backtrack(sequence, used, 0, n);
        
        // Return the constructed sequence
        return sequence;
    }
};

Python

class Solution:
    # Backtracking function to fill the sequence
    def backtrack(self, sequence, used, currentIndex, n):
        # If we've filled all required positions, the sequence is complete
        if currentIndex >= 2 * n - 1:
            return True

        # Skip already filled positions
        if sequence[currentIndex] != -1:
            return self.backtrack(sequence, used, currentIndex + 1, n)

        # Try placing numbers from n down to 1
        for currentNum in range(n, 0, -1):
            # Skip numbers that have already been used
            if used[currentNum]:
                continue

            # Ensure there's enough space to place the currentNum at the required distance
            if currentNum != 1 and (currentIndex + currentNum >= 2 * n - 1 or sequence[currentIndex + currentNum] != -1):
                continue

            # Mark the current number as used
            used[currentNum] = True

            # Place the current number in the sequence
            if currentNum == 1:
                sequence[currentIndex] = currentNum
            else:
                sequence[currentIndex] = sequence[currentIndex + currentNum] = currentNum

            # Continue the backtracking for the next index
            if self.backtrack(sequence, used, currentIndex + 1, n):
                return True

            # Revert changes if placing currentNum didn't lead to a solution
            if currentNum != 1:
                sequence[currentIndex + currentNum] = -1
            used[currentNum] = False
            sequence[currentIndex] = -1
        return False

    # Main function to construct the lexicographically largest sequence
    def constructDistancedSequence(self, n):
        # Initialize the sequence with -1 to denote empty positions
        sequence = [-1] * (2 * n - 1)
        
        # Initialize a boolean array to track used numbers
        used = [False] * (n + 1)
        
        # Start backtracking from index 0
        self.backtrack(sequence, used, 0, n)
        
        # Return the constructed sequence
        return sequence

Complexity

  • Time complexity: $O(n!)$

    The time complexity of this solution is determined by the backtracking approach. In the worst case, the algorithm tries placing numbers from $n$ down to $1$, and for each number, it checks all possible positions. As the function explores all permutations to find a valid sequence, it can be approximated by $O(n!)$, where $n$ is the input integer. This complexity arises because for higher values of $n$, the number of permutations explored increases factorially.

  • Space complexity: $O(n)$

    The space complexity is primarily due to the additional storage used by the recursive call stack and the storage of the sequence and used vectors. The sequence vector requires $O(2n - 1) \approx O(n)$ space, and the used vector requires $O(n)$ space. As a result, the overall space complexity is $O(n)$.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.