1718. Construct the Lexicographically Largest Valid Sequence LeetCode Solution

In this guide, you will get 1718. Construct the Lexicographically Largest Valid Sequence LeetCode Solution with the best time and space complexity. The solution to Construct the Lexicographically Largest Valid Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Construct the Lexicographically Largest Valid Sequence solution in C++
Construct the Lexicographically Largest Valid Sequence solution in Java
Construct the Lexicographically Largest Valid Sequence solution in Python
Additional Resources

1718. Construct the Lexicographically Largest Valid Sequence LeetCode Solution image

Problem Statement of Construct the Lexicographically Largest Valid Sequence

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.

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

Complexity Analysis

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

1718. Construct the Lexicographically Largest Valid Sequence LeetCode Solution in C++

class Solution {
 public:
  vector<int> constructDistancedSequence(int n) {
    vector<int> ans(2 * n - 1);
    dfs(n, 0, 0, ans);
    return ans;
  }

 private:
  bool dfs(int n, int i, int mask, vector<int>& ans) {
    if (i == ans.size())
      return true;
    if (ans[i] > 0)
      return dfs(n, i + 1, mask, ans);

    // Greedily fill in `ans` in descending order.
    for (int num = n; num >= 1; --num) {
      if (mask >> num & 1)
        continue;
      if (num == 1) {
        ans[i] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i] = 0;
      } else {  // num in [2, n]
        if (i + num >= ans.size() || ans[i + num] > 0)
          continue;
        ans[i] = num;
        ans[i + num] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i + num] = 0;
        ans[i] = 0;
      }
    }

    return false;
  }
};
/* code provided by PROGIEZ */

1718. Construct the Lexicographically Largest Valid Sequence LeetCode Solution in Java

class Solution {
  public int[] constructDistancedSequence(int n) {
    int[] ans = new int[2 * n - 1];
    dfs(n, 0, 0, ans);
    return ans;
  }

  private boolean dfs(int n, int i, int mask, int[] ans) {
    if (i == ans.length)
      return true;
    if (ans[i] > 0)
      return dfs(n, i + 1, mask, ans);

    // Greedily fill in `ans` in descending order.
    for (int num = n; num >= 1; --num) {
      if ((mask >> num & 1) == 1)
        continue;
      if (num == 1) {
        ans[i] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i] = 0;
      } else { // num in [2, n]
        if (i + num >= ans.length || ans[i + num] > 0)
          continue;
        ans[i] = num;
        ans[i + num] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i + num] = 0;
        ans[i] = 0;
      }
    }

    return false;
  }
}
// code provided by PROGIEZ

1718. Construct the Lexicographically Largest Valid Sequence LeetCode Solution in Python

class Solution:
  def constructDistancedSequence(self, n: int) -> list[int]:
    ans = [0] * (2 * n - 1)

    def dfs(i: int, mask: int) -> bool:
      if i == len(ans):
        return True
      if ans[i] > 0:
        return dfs(i + 1, mask)

      # Greedily fill in `ans` in descending order.
      for num in range(n, 0, -1):
        if (mask >> num & 1) == 1:
          continue
        if num == 1:
          ans[i] = num
          if dfs(i + 1, mask | 1 << num):
            return True
          ans[i] = 0
        else:  # num in [2, n]
          if i + num >= len(ans) or ans[i + num] > 0:
            continue
          ans[i] = num
          ans[i + num] = num
          if dfs(i + 1, mask | 1 << num):
            return True
          ans[i + num] = 0
          ans[i] = 0

      return False

    dfs(0, 0)
    return ans
 # code by PROGIEZ