Construct the Lexicographically Largest Valid Sequence

Posted: 12 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a positive integer N. Your task is to create the lexicographically largest sequence of length 2*N - 1 containing integers between 1 to N such that:

1. 1 occurs in the sequence exactly once.
2. Each integer between 2 to N(inclusive) occurs in the sequence exactly twice.
3. For each integer i between 2 to N, the distance between the two occurrences of i should be exactly i.

Note:

1. 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.
2. It is guaranteed that under the given constraints, there is always a solution. 
Input Format:
The first line contains an integer, ‘T’ which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and the only line of each test case contains one integer N, as described in the problem statement.
Output Format:
For each test case, print in a new line, 2*'N' - 1 space-separated integer representing the lexicographically largest sequence for the given input.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 20

Time Limit: 1 second
Approach 1

Approach:

 

In this approach, we will be trying to find the valid sequence using backtracking. We will be creating our sequence from left to right and will be trying to fix the biggest possible integer yet to be used at the current position. We are fixing the biggest integer first because that will give us the lexicographically largest sequence that is possible. For every position, we will be fixing the biggest unused integer till now at the current position and then mark this integer as used and will try to create the remaining sequence from the next position. If the sequence is not possible by fixing the biggest integer, then we will try to fix the next biggest integer at the current position and again try to create the remaining sequence and do this till we find a valid answer. The first valid sequence that we will find in this way will automatically be the lexicographically largest sequence.

 

Steps:

  1. Create an array named ‘ANSWER’ of size '2*N - 1' initialized with 0 that will store our sequence.
  2. Create another array named ‘REMAINING’ of size ‘N + 1’ initialized with 1 that will indicate whether an integer is used or not.
  3. Create a function named findValidSequence(ANSWER, REMAINING, INDEX) that will return the lexicographically largest valid sequence, where the ‘INDEX’ is the current position in the ‘ANSWER array.
  4. Call the function findValidSequence(ANSWER, REMAINING, 0) and return it’s output.

 

findValidSequence(ANSWER[], REMAINING[], INDEX) :

 

  1. If ‘INDEX’ == ‘ANSWER.size()’ :
    • return ‘ANSWER’
  2. If ‘ANSWER[INDEX]’ is already fixed :
    • return findValidSequence(ANSWER, REMAINING, INDEX + 1):
  3. Run a loop from ‘i’ = ‘REMAINING.size() - 1’ to 0  and do:
    • If ‘REMAINING[i]’ is already used :
      • Skip the iteration.
    • If ‘i’ is not 1 AND ‘INDEX’ + ‘i’ < ‘ANSWER.size()’ and ‘ANSWER[INDEX + i]’ is not yet fixed:
      • ‘ANSWER[INDEX]’ = ‘ANSWER[INDEX + i]’ = ‘i’.
      • Mark ‘REMAINING[i]’ as used.
      • ‘TEMPANSWER’ = findValidSequence(ANSWER, REMAINING, INDEX + 1)
      • If ‘TEMPANSWER’ is not empty :
        • return ‘TEMPANSWER’
      • Mark ‘REMAINING[i]' as unused.
      • ‘ANSWER[INDEX]’ = ‘ANSWER[INDEX + i]’ = 0.
    • If ‘i’ is 1 :
      • ‘ANSWER[INDEX]’ = ‘i’.
      • Mark ‘REMAINING[i]’ as used.
      • ‘TEMPANSWER’ = findValidSequence(ANSWER, REMAINING, INDEX + 1)
      • If ‘TEMPANSWER’ is not empty :
        • return ‘TEMPANSWER’
      • Mark ‘REMAINING[i]’ as unused.
      • ‘ANSWER[INDEX]’ = 0.
  4. Finally, as we come out of the loop, there is no valid sequence satisfying the conditions. Hence, we return an empty array.
Try Problem