Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1718.html
1718. Construct the Lexicographically Largest Valid Sequence
Level
Medium
Description
Given an integer n, find a sequence that satisfies all of the following:
- The integer
1occurs once in the sequence. - Each integer between
2andnoccurs twice in the sequence. - For every integer
ibetween2andn, the distance between the two occurrences ofiis exactlyi.
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
Solution
Use backtrack. Put the numbers into the sequence, from n to 1, starting from the current index. For each index, always try the maximum possible number so that the sequence is the lexicographically largest one.
-
class Solution { public int[] constructDistancedSequence(int n) { int length = n * 2 - 1; int[] sequence = new int[length]; Set<Integer> visited = new HashSet<Integer>(); backtrack(sequence, visited, 0, n, length); return sequence; } public boolean backtrack(int[] sequence, Set<Integer> visited, int start, int n, int length) { if (visited.size() == n) return true; if (sequence[start] > 0) return backtrack(sequence, visited, start + 1, n, length); for (int i = n; i > 0; i--) { if (!visited.contains(i)) { int next = start + i; if (i == 1 || next < length && sequence[next] == 0) { sequence[start] = i; if (i > 1) sequence[next] = i; visited.add(i); if (backtrack(sequence, visited, start + 1, n, length)) return true; sequence[start] = 0; if (i > 1) sequence[next] = 0; visited.remove(i); } } } return false; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/ // Time: O(N!) // Space: O(N) class Solution { public: vector<int> constructDistancedSequence(int n) { vector<int> ans(2 * n - 1), used(n + 1, 0); function<bool(int i)> dfs = [&](int i) -> bool { if (i == ans.size()) return true; if (ans[i]) return dfs(i + 1); for (int j = n; j >= 1; --j) { if (used[j] || (j != 1 && (i + j >= ans.size() || ans[i + j]))) continue; used[j] = 1; ans[i] = j; if (j != 1) ans[i + j] = j; if (dfs(i + 1)) return true; ans[i] = used[j] = 0; if (j != 1) ans[i + j] = 0; } return false; }; dfs(0); return ans; } }; -
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:] ############ # 1718. Construct the Lexicographically Largest Valid Sequence # https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/ class Solution: def constructDistancedSequence(self, n: int): length = 1 + (n-1)*2 res = [0] * length used = set() def backtrack(idx): if idx == length: return True if res[idx]: if backtrack(idx+1): return True return False for i in range(n, 0, -1): if i in used: continue if i == 1: res[idx] = i used.add(i) if backtrack(idx+1): return True res[idx] = 0 used.remove(i) else: if i + idx >= length or res[i+idx]: continue res[idx] = i res[idx+i] = i used.add(i) if backtrack(idx+1): return True res[idx] = 0 res[idx+i] = 0 used.remove(i) return False backtrack(0) return res -
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:] }