Problem Statement in English

You are given an array nums of length n. You need to sort the array in non-decreasing order based on the sum of the digits of each number. If two numbers have the same digit sum, they should be sorted by their original order in the array. You need to find the minimum number of swaps required to sort the array in this manner.

Approach

The most important thing is to realize that this is a sorting problem. The array needs to be sorted based on the sum of the digits of each number. If two numbers have the same digit sum, they should be sorted by their original order in the array.

In order to figure out the number of swaps needed, we need to use the sorted array as reference. For each index in the original array, we need to check if the number at that index is the same as the number at that index in the sorted array. If it is not, we need to swap it with the number that should be at that index in the sorted array.

To optimize the process, we can use a hashmap to keep track of the indices of the numbers in the original array. This way, we can quickly find the index of the number that should be at a given index in the sorted array.

Solution in Python


class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        reference = sorted(nums, key=lambda x: (sum(map(int, str(x))), x))

        hm = {}

        for i, num in enumerate(nums):
            hm[num] = i

        swaps = 0

        for i in range(len(nums)):
            current = nums[i]
            ref = reference[i]

            if current == ref:
                continue

            nums[hm[ref]] = current
            hm[current] = hm[ref]
            swaps += 1

        return swaps

Complexity

  • Time: $O(nlogn)$
    Since we are sorting the array, the time complexity is $O(nlogn)$.

  • Space: $O(n)$
    Since we use a hashmap to keep track of the indices of the numbers in the original array, the space complexity is $O(n)$.

Mistakes I Made

I needed a hint for this one :(

And we are done.