LeetCode 3551 - Minimum Swaps to Sort by Digit Sum

The problem asks us to sort an array of distinct positive integers not by their natural numeric value, but by the sum of their digits. If two numbers share the same digit sum, the smaller number must come first.

leetcodemediumarrayhash-tablesorting

LeetCode Problem 3551

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to sort an array of distinct positive integers not by their natural numeric value, but by the sum of their digits. If two numbers share the same digit sum, the smaller number must come first. After determining this sorted order, we must calculate the minimum number of swaps needed to transform the original array into this order. A swap exchanges the elements at two positions in the array.

The input is a list nums of size up to 10^5 where each number can be as large as 10^9. The distinctness of the numbers guarantees that no two elements are exactly equal, which simplifies mapping positions to cycles. The output is a single integer representing the minimum swaps.

Important edge cases include arrays that are already sorted by digit sum, arrays with numbers that share digit sums, and arrays of length 1 (where no swaps are required). The problem guarantees distinct numbers, so we do not need to handle duplicates.

The core difficulty is computing the minimum number of swaps efficiently. Naively sorting the array and swapping in a greedy manner can be slow for large arrays, so a better approach relies on understanding the permutation cycles induced by the target order.

Approaches

The brute-force approach involves repeatedly scanning the array to place each number in its correct position according to the digit sum. For each misplaced number, we swap it with the number that should occupy its place. This approach works because each swap moves at least one number into its correct position. However, repeatedly searching for the correct position is O(n^2), which is too slow for n up to 10^5.

The optimal approach recognizes that the problem reduces to computing the minimum swaps to sort an array of distinct elements. We can compute the target sorted order based on digit sums, create a mapping from each number to its position in this sorted array, and then count the number of cycles in this permutation. The size of each cycle of length k contributes k - 1 swaps. This approach is O(n log n) due to sorting, and it efficiently handles large inputs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Swap elements repeatedly to reach sorted order; too slow for large arrays
Optimal O(n log n) O(n) Sort by digit sum, map positions, compute cycles to count swaps

Algorithm Walkthrough

  1. Compute the digit sum of each number in nums. This will be used as the primary key for sorting.
  2. Create a list of tuples (num, index, digit_sum) to retain both the original index and the number itself. This allows tracking where each number should go after sorting.
  3. Sort this list first by digit_sum and then by the number itself. This defines the target sorted order.
  4. Build a mapping from each original index to the index in the sorted array. This creates a permutation array representing where each element needs to move.
  5. Initialize a visited array of size n to keep track of which elements have been processed in cycles.
  6. Iterate over each index. If it has not been visited, traverse the cycle starting from this index. Count the length of the cycle. Each cycle of length k requires k - 1 swaps to resolve.
  7. Sum the swaps required for all cycles to obtain the minimum total swaps.

Why it works: Sorting the array based on the digit sum produces the final order. Each element is part of exactly one cycle in the permutation mapping from the original array to the sorted array. Resolving all cycles ensures each element reaches its correct position with the fewest swaps possible.

Python Solution

from typing import List

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        def digit_sum(x: int) -> int:
            total = 0
            while x > 0:
                total += x % 10
                x //= 10
            return total
        
        n = len(nums)
        arr = [(num, i, digit_sum(num)) for i, num in enumerate(nums)]
        arr.sort(key=lambda x: (x[2], x[0]))
        
        pos_map = [0] * n
        for new_idx, (_, orig_idx, _) in enumerate(arr):
            pos_map[orig_idx] = new_idx
        
        visited = [False] * n
        swaps = 0
        
        for i in range(n):
            if visited[i] or pos_map[i] == i:
                continue
            cycle_size = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = pos_map[j]
                cycle_size += 1
            swaps += cycle_size - 1
        
        return swaps

This solution first calculates the digit sum for each number and sorts by it. The pos_map array represents the permutation from original indices to sorted indices. Then, we count swaps by traversing each cycle in the permutation.

Go Solution

func minSwaps(nums []int) int {
    n := len(nums)
    
    digitSum := func(x int) int {
        sum := 0
        for x > 0 {
            sum += x % 10
            x /= 10
        }
        return sum
    }
    
    type Elem struct {
        num       int
        origIndex int
        dsum      int
    }
    
    arr := make([]Elem, n)
    for i, num := range nums {
        arr[i] = Elem{num, i, digitSum(num)}
    }
    
    sort.Slice(arr, func(i, j int) bool {
        if arr[i].dsum == arr[j].dsum {
            return arr[i].num < arr[j].num
        }
        return arr[i].dsum < arr[j].dsum
    })
    
    posMap := make([]int, n)
    for newIdx, e := range arr {
        posMap[e.origIndex] = newIdx
    }
    
    visited := make([]bool, n)
    swaps := 0
    
    for i := 0; i < n; i++ {
        if visited[i] || posMap[i] == i {
            continue
        }
        cycleSize := 0
        j := i
        for !visited[j] {
            visited[j] = true
            j = posMap[j]
            cycleSize++
        }
        swaps += cycleSize - 1
    }
    
    return swaps
}

In Go, we use a struct Elem to store the original index and digit sum. Sorting uses sort.Slice with a custom comparator. Otherwise, the cycle-counting logic mirrors Python exactly.

Worked Examples

Example 1: nums = [37, 100]

Index Num Digit Sum Sorted Index
0 37 10 1
1 100 1 0

Permutation: [1, 0], one cycle of length 2 → 1 swap.

Example 2: nums = [22, 14, 33, 7]

Index Num Digit Sum Sorted Index
0 22 4 0
1 14 5 1
2 33 6 2
3 7 7 3

Permutation: [0, 1, 2, 3], all elements in place → 0 swaps.

Example 3: nums = [18, 43, 34, 16]

Index Num Digit Sum Sorted Index
0 18 9 3
1 43 7 2
2 34 7 1
3 16 7 0

Cycles: [0->3->0] length 2, [1->2->1] length 2 → total 2 swaps.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting by digit sum dominates; computing digit sum is O(log maxNum) per number, which is ≤ O(n) for given constraints
Space O(n) Stores tuple of (num, index, digit sum) and visited array

Sorting dominates the runtime. Cycle counting is O(n), so overall time is O(n log n). Memory usage scales linearly with input size due to auxiliary arrays.

Test Cases

# Provided examples
assert Solution().minSwaps([37, 100]) == 1  # Example 1
assert Solution().minSwaps([22, 14, 33, 7]) == 0  # Example 2
assert Solution().minSwaps([18, 43, 34, 16]) == 2  # Example 3

# Edge cases
assert Solution().minSwaps([5]) == 0  # Single element, no swaps
assert Solution().minSwaps([11, 2, 20, 101]) == 2  # Different digit sums, requires swaps
assert Solution().minSwaps([111, 12, 21]) == 1  # Same digit sums, tie broken by number
assert Solution().minSwaps([9