1718. Construct the Lexicographically Largest Valid Sequence

[mah-shamim]

Topics: Array, Backtracking

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

Hint:

1. Heuristic algorithm may work.

[mah-shamim]

We need to construct the lexicographically largest valid sequence that satisfies specific constraints. The sequence must include the integer 1 once and each integer from 2 to n exactly twice, with the distance between their occurrences equal to their value.

Approach

The approach uses a backtracking algorithm to build the sequence step-by-step, ensuring that each number is placed in the highest possible position to achieve the lexicographically largest sequence. The key steps are:

1. Track Usage and Reservations: Use arrays to track which numbers have been used and their positions, and which positions are reserved for subsequent occurrences of a number.
2. Backtracking: Recursively attempt to place each number starting from the largest possible value (n) down to 1. This ensures that the lexicographically largest sequence is found first.
3. Reserve Positions: When placing the first occurrence of a number, reserve the position where the second occurrence must be placed. This ensures the correct distance between the two occurrences.

Let's implement this solution in PHP: 1718. Construct the Lexicographically Largest Valid Sequence

<?php
/**
 * @param Integer $n
 * @return Integer[]
 */
function constructDistancedSequence($n) {
    $length = 2 * $n - 1;
    $sequence = array_fill(0, $length, 0);
    $used = array_fill(0, $n + 1, 0); // used[0] unused
    $reserved = array_fill(0, $length, null);

    $success = backtrack(0, $sequence, $used, $reserved, $n);

    return $success ? $sequence : [];
}

/**
 * @param $current_pos
 * @param $sequence
 * @param $used
 * @param $reserved
 * @param $n
 * @return bool
 */
function backtrack($current_pos, &$sequence, &$used, &$reserved, $n) {
    $length = 2 * $n - 1;
    if ($current_pos >= $length) {
        return true;
    }

    if ($sequence[$current_pos] != 0) {
        return backtrack($current_pos + 1, $sequence, $used, $reserved, $n);
    }

    if ($reserved[$current_pos] !== null) {
        $num = $reserved[$current_pos];
        if ($used[$num] != 1) {
            return false;
        }
        // Place the second occurrence
        $sequence[$current_pos] = $num;
        $used[$num] = 2;
        $success = backtrack($current_pos + 1, $sequence, $used, $reserved, $n);
        if ($success) {
            return true;
        } else {
            $sequence[$current_pos] = 0;
            $used[$num] = 1;
            return false;
        }
    } else {
        // Try placing numbers from n down to 1
        for ($num = $n; $num >= 1; $num--) {
            if ($num == 1) {
                if ($used[1] == 0) {
                    $sequence[$current_pos] = 1;
                    $used[1] = 1;
                    $success = backtrack($current_pos + 1, $sequence, $used, $reserved, $n);
                    if ($success) {
                        return true;
                    }
                    $sequence[$current_pos] = 0;
                    $used[1] = 0;
                }
            } else {
                if ($used[$num] == 0) {
                    $next_pos = $current_pos + $num;
                    if ($next_pos < $length && $sequence[$next_pos] == 0 && $reserved[$next_pos] === null) {
                        $sequence[$current_pos] = $num;
                        $used[$num] = 1;
                        $reserved[$next_pos] = $num;
                        $success = backtrack($current_pos + 1, $sequence, $used, $reserved, $n);
                        if ($success) {
                            return true;
                        }
                        $sequence[$current_pos] = 0;
                        $used[$num] = 0;
                        $reserved[$next_pos] = null;
                    }
                }
            }
        }
        return false;
    }
}

// Test cases
print_r(constructDistancedSequence(3));
print_r(constructDistancedSequence(5));
?>

Explanation:

1. Initialization: The constructLargestValidSequence function initializes the necessary arrays and starts the backtracking process from position 0.
2. Backtracking Function: The backtrack function handles placing numbers in the sequence:
   • If the current position is reserved, it places the required number and checks if the rest of the sequence can be filled.
   • If not reserved, it tries placing numbers from n down to 1, ensuring the largest possible number is placed first.
   • For each number, it checks if the next occurrence can be placed at the correct reserved position, ensuring the distance constraint is met.

This approach efficiently explores possible sequences while ensuring the lexicographically largest valid sequence is found first.

[topugit]

Thanks for solving the problem of "Construct the Lexicographically Largest Valid Sequence"

[mah-shamim]

Thanks