Today’s problem

https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/description/

Intuition

  • In this question, we are doing a sorting process that only difference less than limit can swap.
  • Therefore, there forms “groups”. In a group, two sequential number has a difference less than limit.
  • In this case, if we sort the numbers in a group, then we are all done.

Approach

  1. We need to get the groups.
  2. We need to sort the array first.
  3. Then if the difference between two numbers are bigger than limit, then it would belong to two different groups.
  4. Then we sort the result for each group.

Complexity

  • Time complexity: $O(N\times log(N))$, N is the length of the array.

  • Space complexity: $O(N)$

Code

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        sorted_nums = []
        for idx, x in enumerate(nums):
            sorted_nums.append((x, idx))
        sorted_nums.sort()

        # First we sort the array
        
        groups = []
        tmp = []
        for i in range(len(nums)):
            if i > 0 and sorted_nums[i][0] - sorted_nums[i-1][0] > limit:
                tmp.sort()
                groups.append(tmp)
                tmp = []

            tmp.append(sorted_nums[i][1])
        
        tmp.sort()
        groups.append(tmp)

        # Then we form groups

        idx = 0
        pos = 0
        ans = [0] * len(nums)
        for i in range(len(nums)):
            if pos == len(groups[idx]):
                pos = 0
                idx += 1

            ans[groups[idx][pos]] = sorted_nums[i][0]
            pos += 1

        # Then we sort the groups
        
        return ans