We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct the Lexicographically Largest Valid Sequence

Number: 1819

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta

Problem Description

Given an integer n, construct a sequence of length (2n - 1) with numbers in the range [1, n] such that:

  • The number 1 appears exactly once.
  • For each number i (2 ≤ i ≤ n), it appears exactly twice.
  • For each i (2 ≤ i ≤ n), the distance (absolute difference in indices) between its two occurrences is exactly i. Among all valid sequences, return the lexicographically largest one.

Key Insights

  • To achieve the lexicographically largest sequence, try to place larger numbers as early as possible.
  • Since numbers must be placed exactly twice (except for 1, which is placed once), when placing a number i (i > 1), reserve two positions: one at index pos and the other at index pos+i, ensuring the required gap.
  • Use backtracking to try placements while following the sequence constraints.
  • Use a global state (or shared data structure) to mark numbers as used.
  • Skip already filled positions to reduce unnecessary work during recursion.

Space and Time Complexity

Time Complexity: Exponential in the worst-case due to backtracking; however, the constrained n (1 ≤ n ≤ 20) keeps the problem tractable. Space Complexity: O(n) for the recursion stack and an auxiliary array of size O(2n).

Solution

We solve this problem using a backtracking approach. We create an array of size (2n - 1) initialized with a placeholder value (e.g. -1) to indicate unfilled positions. Then we recursively try to place numbers from n down to 1 (to favor lexicographically larger sequences) as follows:

  1. For each unfilled index, attempt to put a number that hasn’t been used:
    • If the number is 1, it requires only one position.
    • For numbers greater than 1, ensure that the partner position (current index + i) is available and within bounds.
  2. Mark the number as used, place it (and its partner for numbers > 1), and move to the next index.
  3. If the placement leads to a dead-end, backtrack by unmarking the number and resetting the positions.
  4. The algorithm stops when all positions are filled, ensuring the lexicographically largest valid sequence.

Code Solutions

# Python solution using backtracking

def constructLargestSequence(n):
    # Initialize the result list with -1 representing empty spots
    res = [-1] * (2 * n - 1)
    # Array to mark whether a number has been placed
    used = [False] * (n + 1)

    def backtrack(pos):
        # If we've filled all positions, we're done
        if pos == len(res):
            return True
        # If this position is already filled, move to the next one
        if res[pos] != -1:
            return backtrack(pos + 1)
        # Try to place numbers from n down to 1 for lexicographical order
        for num in range(n, 0, -1):
            if used[num]:
                continue  # Skip numbers that have been placed
            if num == 1:
                res[pos] = 1  # 1 occurs only once
                used[1] = True
                if backtrack(pos + 1):
                    return True
                # Backtrack: remove placement
                res[pos] = -1
                used[1] = False
            else:
                # Ensure the second occurrence position is valid and empty
                second_pos = pos + num
                if second_pos < len(res) and res[second_pos] == -1:
                    res[pos] = num
                    res[second_pos] = num
                    used[num] = True
                    if backtrack(pos + 1):
                        return True
                    # Backtrack the placement for current number
                    res[pos] = -1
                    res[second_pos] = -1
                    used[num] = False
        return False

    backtrack(0)
    return res

# Example usage:
# print(constructLargestSequence(3))
← Back to All Questions