Welcome to Subscribe On Youtube

1718. Construct the Lexicographically Largest Valid Sequence

Description

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

Solutions

DFS.

• Java
• C++
• Python
• Go

• class Solution {
      private int[] path;
      private int[] cnt;
      private int n;
  
      public int[] constructDistancedSequence(int n) {
          this.n = n;
          path = new int[n * 2];
          cnt = new int[n * 2];
          Arrays.fill(cnt, 2);
          cnt[1] = 1;
          dfs(1);
          int[] ans = new int[n * 2 - 1];
          for (int i = 0; i < ans.length; ++i) {
              ans[i] = path[i + 1];
          }
          return ans;
      }
  
      private boolean dfs(int u) {
          if (u == n * 2) {
              return true;
          }
          if (path[u] > 0) {
              return dfs(u + 1);
          }
          for (int i = n; i > 1; --i) {
              if (cnt[i] > 0 && u + i < n * 2 && path[u + i] == 0) {
                  cnt[i] = 0;
                  path[u] = i;
                  path[u + i] = i;
                  if (dfs(u + 1)) {
                      return true;
                  }
                  cnt[i] = 2;
                  path[u] = 0;
                  path[u + i] = 0;
              }
          }
          if (cnt[1] > 0) {
              path[u] = 1;
              cnt[1] = 0;
              if (dfs(u + 1)) {
                  return true;
              }
              cnt[1] = 1;
              path[u] = 0;
          }
          return false;
      }
  }
  

• class Solution {
  public:
      int n;
      vector<int> cnt, path;
  
      vector<int> constructDistancedSequence(int _n) {
          n = _n;
          cnt.resize(n * 2, 2);
          path.resize(n * 2);
          cnt[1] = 1;
          dfs(1);
          vector<int> ans;
          for (int i = 1; i < n * 2; ++i) ans.push_back(path[i]);
          return ans;
      }
  
      bool dfs(int u) {
          if (u == n * 2) return 1;
          if (path[u]) return dfs(u + 1);
          for (int i = n; i > 1; --i) {
              if (cnt[i] && u + i < n * 2 && !path[u + i]) {
                  path[u] = path[u + i] = i;
                  cnt[i] = 0;
                  if (dfs(u + 1)) return 1;
                  cnt[i] = 2;
                  path[u] = path[u + i] = 0;
              }
          }
          if (cnt[1]) {
              path[u] = 1;
              cnt[1] = 0;
              if (dfs(u + 1)) return 1;
              cnt[1] = 1;
              path[u] = 0;
          }
          return 0;
      }
  };
  

• class Solution:
      def constructDistancedSequence(self, n: int) -> List[int]:
          def dfs(u):
              if u == n * 2:
                  return True
              if path[u]:
                  return dfs(u + 1)
              for i in range(n, 1, -1):
                  if cnt[i] and u + i < n * 2 and path[u + i] == 0:
                      cnt[i] = 0
                      path[u] = path[u + i] = i
                      if dfs(u + 1):
                          return True
                      path[u] = path[u + i] = 0
                      cnt[i] = 2
              if cnt[1]:
                  cnt[1], path[u] = 0, 1
                  if dfs(u + 1):
                      return True
                  path[u], cnt[1] = 0, 1
              return False
  
          path = [0] * (n * 2)
          cnt = [2] * (n * 2)
          cnt[1] = 1
          dfs(1)
          return path[1:]
  
  

• func constructDistancedSequence(n int) []int {
  	path := make([]int, n*2)
  	cnt := make([]int, n*2)
  	for i := range cnt {
  		cnt[i] = 2
  	}
  	cnt[1] = 1
  	var dfs func(u int) bool
  	dfs = func(u int) bool {
  		if u == n*2 {
  			return true
  		}
  		if path[u] > 0 {
  			return dfs(u + 1)
  		}
  		for i := n; i > 1; i-- {
  			if cnt[i] > 0 && u+i < n*2 && path[u+i] == 0 {
  				cnt[i] = 0
  				path[u], path[u+i] = i, i
  				if dfs(u + 1) {
  					return true
  				}
  				cnt[i] = 2
  				path[u], path[u+i] = 0, 0
  			}
  		}
  		if cnt[1] > 0 {
  			cnt[1] = 0
  			path[u] = 1
  			if dfs(u + 1) {
  				return true
  			}
  			cnt[1] = 1
  			path[u] = 0
  		}
  		return false
  	}
  	dfs(1)
  	return path[1:]
  }
  

All Problems

All Solutions