aboutsummaryrefslogtreecommitdiff
path: root/make_lex_small_arr.py
blob: 565469dec660f1da21ff32abc7fad5472697f16e (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
# 2948. Make Lexicographically Smallest Array by Swapping Elements

"""
you are given a 0-indexed array of positive integers 'nums' and a positive
integer 'limit'. in one operation, you can choose any two indices 'i' and 'j'
and swap 'nums[i]' and 'nums[j]' if '|nums[i] - nums[j]| <= limit'. return
the lexicographically smallest array that can be obtained by performingthe
operation any number of times.
"""


class Solution(object):
    def lexicographicallySmallestArray(self, nums, limit):
        """
        :type nums: List[int]
        :type limit: int
        :rtype: List[int]
        """
        n, indices = len(nums), []
        cpy, ans = sorted([(nums[i], i) for i in range(n)]), [0] * n
        for i in range(n):
            if i == 0 or cpy[i][0] - cpy[i - 1][0] > limit:
                indices.append([])
            indices[-1].append(cpy[i][1])
        for i in indices:
            curr = sorted(i)
            for j in range(len(i)):
                ans[curr[j]] = nums[i[j]]
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.lexicographicallySmallestArray(nums=[1, 5, 3, 9, 8], limit=2))
    print(obj.lexicographicallySmallestArray(nums=[1, 7, 6, 18, 2, 1], limit=3))
    print(obj.lexicographicallySmallestArray(nums=[1, 7, 28, 19, 10], limit=3))