Medium

Minimum Swaps to Sort by Digit Sum

LAB

Sort numbers by digit sum, then value. Return the minimum swaps needed to transform nums into that order.

EXAMPLES

Example 1

Input
{
  "nums": [
    37,
    100
  ]
}

Output
1

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Note in this example we don't just want regular sorted order, but sorted order depending on the digit sum. The cycle decomposition technique works regardless of the sorting criteria.

Reveal reference solution +

pythonREFERENCE

def digitSum(self, num):
    return sum(int(d) for d in str(num))

def minSwaps(self, nums):
    n = len(nums)
    # Sort based on (digit sum, value)
    sorted_nums = sorted(nums, key=lambda x: (self.digitSum(x), x))

    # Map original indices to sorted positions
    index_map = {val: i for i, val in enumerate(sorted_nums)}

    visited = [False] * n
    swaps = 0

    for i in range(n):
        if visited[i] or index_map[nums[i]] == i:
            continue

        cycle_size = 0
        j = i
        while not visited[j]:
            visited[j] = True
            j = index_map[nums[j]]
            cycle_size += 1

        if cycle_size > 0:
            swaps += cycle_size - 1

    return swaps

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗