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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct the Lexicographically Largest Valid Sequence

Difficulty: Medium

Problem Description

Given an integer n, find a sequence with elements in the range [1, n] 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.

Return the lexicographically largest sequence.

Key Insights

  • The number 1 must be placed at a position that allows for the largest possible values to be placed around it.
  • The integers from 2 to n must be placed in such a way that their occurrences are exactly i indices apart.
  • To achieve a lexicographically larger sequence, we should start placing larger numbers first.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To construct the lexicographically largest valid sequence:

  1. Start by initializing an array of size 2n-1, as the total length will be 2 times the count of numbers from 2 to n plus one for the number 1.
  2. Place the number 1 in the middle of the sequence.
  3. Iterate from n down to 2:
    • For each number i, determine the first available positions for the two occurrences of i by checking the indices that are exactly i apart.
    • Place the two occurrences of i in the available positions.
  4. The final array will be the lexicographically largest valid sequence.

Code Solutions

def constructLargestSequence(n):
    # Initialize the result array
    result = [0] * (2 * n - 1)
    
    # Place '1' in the middle of the array
    result[n - 1] = 1
    
    # Start placing numbers from n down to 2
    for i in range(n, 1, -1):
        # Place the two occurrences of i
        result[n - i] = i
        result[n - i + i] = i
    
    return result

# Example usage
print(constructLargestSequence(3))  # Output: [3, 1, 2, 3, 2]
print(constructLargestSequence(5))  # Output: [5, 3, 1, 4, 3, 5, 2, 4, 2]
← Back to All Questions