aboutsummaryrefslogtreecommitdiff
path: root/construct_lexicographically_seq.py
blob: 75df73667879cd0ed4e68499922a98df16574413 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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))