Minimum Swaps to Sort by Digit Sum

Minimum Swaps to Sort by Digit Sum

What is this problem about?

The Minimum Swaps to Sort by Digit Sum problem gives you an array of integers. The target ordering is sorted by digit sum (sum of all digits of each number), with ties broken by the original value. You need to find the minimum number of swaps to transform the original array into this target sorted order. This Minimum Swaps to Sort by Digit Sum coding problem tests custom sorting combined with cycle detection for minimum swaps.

Why is this asked in interviews?

Google asks this to evaluate whether candidates can handle multi-key sorting (digit sum first, value second) and then efficiently compute minimum swaps using the cycle detection technique. The array, hash table, and sorting interview pattern is layered here, and the cycle detection insight separates candidates who know this classic graph-on-permutations technique.

Algorithmic pattern used

Custom sort + cycle detection. First, create the target sorted array (by digit sum, then value). Map each element's target position using a hash map. Then treat the permutation — current positions to target positions — as a directed graph. Each connected component (cycle) of length L requires L - 1 swaps to resolve. Sum up (cycle length - 1) across all cycles for the total minimum swaps.

Example explanation

Array: [21, 12, 3]. Digit sums: 21→3, 12→3, 3→3. Tie-break by value: sorted = [3, 12, 21]. Current: [21, 12, 3] → Target: [3, 12, 21].

• 21 is at index 0, should go to index 2.
• 12 is at index 1, already at index 1 (stays).
• 3 is at index 2, should go to index 0. Cycle: 0 → 2 → 0 (length 2). Swaps = 2-1 = 1.

Common mistakes candidates make

• Using bubble sort or selection sort simulation instead of cycle detection (O(n²) vs O(n)).
• Not handling duplicate digit sums correctly when determining target positions.
• Misidentifying cycle lengths when elements map to themselves (cycle length 1 = 0 swaps).
• Using a hash map incorrectly when duplicate elements exist.

Interview preparation tip

"Minimum swaps to sort" problems almost universally use cycle detection on the permutation graph. Internalize this pattern: build a graph where each node points to where its element needs to go, find all cycles, and sum (cycle_length - 1). The tricky part is always in building the correct target permutation — make sure your custom comparator handles ties correctly. Practice this technique across different sorting keys (digit sum, character count, parity) to build fluency.