aboutsummaryrefslogtreecommitdiff
path: root/construct_lexicographically_seq.py
diff options
context:
space:
mode:
Diffstat (limited to 'construct_lexicographically_seq.py')
-rw-r--r--construct_lexicographically_seq.py59
1 files changed, 59 insertions, 0 deletions
diff --git a/construct_lexicographically_seq.py b/construct_lexicographically_seq.py
new file mode 100644
index 0000000..75df736
--- /dev/null
+++ b/construct_lexicographically_seq.py
@@ -0,0 +1,59 @@
+# 1718. Construct the Lexicographically Largest Valid Sequence
+
+"""
+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, and for every integer 'i' between '2' and 'n',
+the distance between the two occurence 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|'.
+"""
+
+
+class Solution(object):
+ def constructDistancedSequence(self, n):
+ """
+ :type n: int
+ :rtype: List[int]
+ """
+ i, arr, vis = 0, [0] * (2 * n - 1), [False] * (n + 1)
+
+ def dfs(arr, i, vis):
+ if i >= 2 * n - 1:
+ return True
+ for j in range(n, 0, -1):
+ if (
+ j > 1
+ and (
+ (not (arr[i] == 0 and (i + j < 2 * n - 1) and arr[i + j] == 0))
+ or vis[j]
+ )
+ ) or (j == 1 and (arr[i] != 0 or vis[j])):
+ continue
+ if j > 1:
+ arr[i] = j
+ arr[i + j] = j
+ else:
+ arr[i] = j
+ vis[j] = True
+ next = i + 1
+ while next < 2 * n - 1 and arr[next]:
+ next += 1
+ if dfs(arr, next, vis):
+ return True
+ if j > 1:
+ arr[i] = 0
+ arr[i + j] = 0
+ else:
+ arr[i] = 0
+ vis[j] = False
+ return False
+
+ dfs(arr, i, vis)
+ return arr
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.constructDistancedSequence(3))
+ print(obj.constructDistancedSequence(5))