LC-2948 Medium LeetCode

2948. Make Lexicographically Smallest Array by Swapping Elements

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 60% Topics: Array, Union Find, Sorting

Reading material

Arrays & Hashing 12 min Union–Find (DSU) 12 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

# sort
class Solution(object):
    def lexicographicallySmallestArray(self, nums, limit):
        """
        :type nums: List[int]
        :type limit: int
        :rtype: List[int]
        """
        idxs = range(len(nums))
        idxs.sort(key=lambda x: nums[x])
        groups = []
        for i in xrange(len(nums)):
            if i-1 < 0 or nums[idxs[i]]-nums[idxs[i-1]] > limit:
                groups.append([])
            groups[-1].append(idxs[i])
        result = [-1]*len(nums)
        for g in groups:
            for i, j in enumerate(sorted(g)):
                result[j] = nums[g[i]]
        return result

Solution from kamyu104/LeetCode-Solutions · MIT