3551. Minimum Swaps to Sort by Digit Sum

Array
Hash Table
Sorting

TIME

O(n log n)

SPACE

O(n)

Intuition

The target arrangement is not ambiguous. The values are distinct, so the key (digit sum, value) is distinct for every element and the sorted order is unique, there is no choice to make about where anything goes. The question is only how cheaply we can get there by swapping.

Minimum swaps between two known arrangements is a cycle-counting problem. Write order[t] for the original index of the element that belongs at position t; this is a permutation of 0..n-1. Decompose it into cycles. Swapping two elements that sit in the same cycle splits that cycle in two; swapping across two cycles merges them into one. We begin with c cycles and have to finish with n (every element a fixed point), so no swap raises the cycle count by more than one and at least n - c swaps are needed. That bound is reached by walking each cycle and putting one element home per swap, so a cycle of length k costs exactly k - 1.

Answer: n - (number of cycles).

Approach

For each index i compute digit_sum(nums[i]) by repeatedly taking % 10 and // 10.
Sort the indices 0..n-1 by (digit_sum, value). Call the result order, so order[t] is the index whose element belongs at position t.
Walk order with a visited array. For each unvisited t, follow t -> order[t] -> order[order[t]] -> ... until it returns, marking as you go, and add length - 1 to the answer.
Return the total.

Fixed points are cycles of length 1 and contribute 0, which is why an already-sorted array needs no special case.

In Java the key and the index are packed into one long (digitSum * 1_000_000_001 + value) << 17 | index so Arrays.sort runs on a primitive long[] instead of boxing into Integer[] with a comparator. Digit sum is at most 81 and value at most 10^9, so the key fits in 37 bits; shifting by 17 leaves room for indices up to 131071, above the 10^5 limit.

Complexity

Time: O(n log n), the sort dominates, cycle counting visits each index once
Space: O(n)

Edge Cases

Already in the target order → every cycle has length 1 → 0, matching example 2
Single element → 0
Equal digit sums → broken by the value, so example 3 sorts [18,43,34,16] to [16,34,43,18] rather than leaving it alone
Values are distinct, so the sort key never ties and order is a genuine permutation; duplicates would make the target order non-unique and this argument would need the cheapest matching instead
Digit sum of a 9-digit number is at most 81, well inside int
A single large cycle costs n - 1 swaps, the worst case

Code

from typing import List


class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        """
        3551. Minimum Swaps to Sort by Digit Sum
        Time: O(n log n)
        Space: O(n)
        """
        n = len(nums)

        def digit_sum(x: int) -> int:
            total = 0
            while x:
                total += x % 10
                x //= 10
            return total

        # order[t] = original index of the element that belongs at position t.
        # Values are distinct, so the key never ties and this is a permutation.
        order = sorted(range(n), key=lambda i: (digit_sum(nums[i]), nums[i]))

        # a cycle of length k needs k - 1 swaps; fixed points cost nothing
        visited = [False] * n
        swaps = 0
        for t in range(n):
            if visited[t]:
                continue
            length = 0
            j = t
            while not visited[j]:
                visited[j] = True
                j = order[j]
                length += 1
            swaps += length - 1

        return swaps

import java.util.Arrays;

/**
 * 3551. Minimum Swaps to Sort by Digit Sum
 * Time: O(n log n)
 * Space: O(n)
 */
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;

        // Pack (digit sum, value) and the index into one long so the sort runs
        // on a primitive array instead of boxing into Integer[] with a
        // comparator. Digit sum <= 81 and value <= 1e9, so the key fits in 37
        // bits; shifting by 17 leaves room for indices up to 131071.
        long[] keyed = new long[n];
        for (int i = 0; i < n; i++) {
            long key = digitSum(nums[i]) * 1_000_000_001L + nums[i];
            keyed[i] = (key << 17) | i;
        }
        Arrays.sort(keyed);

        // order[t] = original index of the element that belongs at position t.
        // Values are distinct, so the key never ties and this is a permutation.
        int[] order = new int[n];
        for (int t = 0; t < n; t++) {
            order[t] = (int) (keyed[t] & 0x1FFFF);
        }

        // a cycle of length k needs k - 1 swaps; fixed points cost nothing
        boolean[] visited = new boolean[n];
        int swaps = 0;
        for (int t = 0; t < n; t++) {
            if (visited[t]) {
                continue;
            }
            int length = 0;
            int j = t;
            while (!visited[j]) {
                visited[j] = true;
                j = order[j];
                length++;
            }
            swaps += length - 1;
        }

        return swaps;
    }

    private int digitSum(int x) {
        int total = 0;
        while (x > 0) {
            total += x % 10;
            x /= 10;
        }
        return total;
    }
}