3551. Minimum Swaps to Sort by Digit Sum

Problem Description

You are given an array nums of distinct positive integers. You need to sort the array in increasing order based on the sum of the digits of each number. If two numbers have the same digit sum, the smaller number appears first in the sorted order.

Return the minimum number of swaps required to rearrange nums into this sorted order.

A swap is defined as exchanging the values at two distinct positions in the array.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The main idea is to recognize that sorting based on a custom rule (sum of digits, then by value) leads to a target arrangement. To find out the minimum number of swaps to reach this arrangement from the original nums, the problem can be seen as rearranging elements by cycles in a permutation. By tracing how each number moves from its original position to its sorted target, each cycle of misplaced numbers of length k can be fixed in k-1 swaps. So, if we can compute these cycles, we can sum up the swaps needed for all cycles to transform the array with the minimum swaps.

Solution Approach

First, calculate the sorting key for each number: compute the sum of its digits. If two numbers have the same digit sum, use the number's value to break ties. Sort the array based on these rules, generating a "target" sorted array.

Next, note where each number in nums should go in the sorted array. Create a mapping from each number to its target position (its index in the sorted array).

The process of figuring out the minimum swaps is equivalent to finding cycles in the positional mapping from the original array to the sorted array. For each number, follow its cycle of positions until you return to the start; a cycle of length k can be corrected in k-1 swaps.

To implement this:

For each number in nums, compute its digit sum.
Sort the numbers using (digit sum, number) as the key.
Map each number to its position in the sorted array.
Using a visited array, for each unvisited position, walk the cycle of swaps needed until you loop back.
Count cycles, and compute total swaps required with the formula n - num_cycles, where n is the array length and num_cycles is the number of cycles found.

This approach efficiently determines the minimum swaps needed, because each swap can place at least one element into its correct position according to the desired order.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the array: nums = [21, 13, 4, 30].

Step 1: Compute the digit sum for each number

21: 2 + 1 = 3
13: 1 + 3 = 4
4: 4
30: 3 + 0 = 3

Step 2: Sort using digit sum, then by value

First compare by digit sum, then by number:

21 (digit sum 3)
30 (digit sum 3)
4 (digit sum 4)
13 (digit sum 4)

Ordering by digit sum, then by value gives: [21, 30, 4, 13].

Step 3: Map each original number to its sorted position

21 is at index 0 (sorted index 0)
13 is at index 1 (sorted index 3)
4 is at index 2 (sorted index 2)
30 is at index 3 (sorted index 1)

Mapping (original index → sorted index): [0, 3, 2, 1]

Step 4: Find cycles in position mapping

Create a visited array: [False, False, False, False].

Start at index 0: 0 → 0 (already in place). Mark as visited.
Index 1: 1 → 3 → 1 (forms a cycle: [1,3]). Mark both as visited. Cycle length: 2.
Index 2: 2 → 2 (already in place). Mark as visited.

Number of cycles: 3

Step 5: Calculate swaps

Total elements = 4. Minimum swaps = 4 - 3 = 1

Answer

Only 1 swap is needed (between indices 1 and 3).

Summary Table

Original	Sorted	Cycle
21 (0)	21 (0)	[0]
13 (1)	30 (3)	[1,3]
4 (2)	4 (2)	[2]
30 (3)	13 (1)	(see above)

A swap between 13 and 30 puts both into their correct positions.

This walkthrough illustrates how digit sum sorting and cycle detection yield the swap count efficiently.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minSwaps(self, nums: List[int]) -> int:
5        # Helper function to compute the sum of digits of an integer
6        def digit_sum(x: int) -> int:
7            total = 0
8            while x:
9                total += x % 10
10                x //= 10
11            return total
12
13        n = len(nums)
14        # Create a sorted list of tuples: (digit sum, original value)
15        sorted_arr = sorted((digit_sum(x), x) for x in nums)
16        # Map each value to its target index in the sorted array
17        value_to_index = {value: idx for idx, (_, value) in enumerate(sorted_arr)}
18        # Initialize the answer as n (maximum number of swaps)
19        swaps = n
20        visited = [False] * n
21
22        # Detect cycles to determine the minimum number of swaps required
23        for i in range(n):
24            if not visited[i]:
25                swaps -= 1
26                j = i
27                while not visited[j]:
28                    visited[j] = True
29                    j = value_to_index[nums[j]]
30        return swaps
31

1class Solution {
2
3    // Main function to find the minimum number of swaps
4    public int minSwaps(int[] nums) {
5        int n = nums.length;
6        int[][] arr = new int[n][2];
7
8        // Construct an array with [sum of digits, original value] for sorting
9        for (int i = 0; i < n; i++) {
10            arr[i][0] = f(nums[i]);
11            arr[i][1] = nums[i];
12        }
13
14        // Sort primarily by sum of digits, then by value
15        Arrays.sort(arr, (a, b) -> {
16            if (a[0] != b[0])
17                return Integer.compare(a[0], b[0]);
18            return Integer.compare(a[1], b[1]);
19        });
20
21        // Map from original value to its target index after sorting
22        Map<Integer, Integer> valueToIndex = new HashMap<>();
23        for (int i = 0; i < n; i++) {
24            valueToIndex.put(arr[i][1], i);
25        }
26
27        boolean[] visited = new boolean[n];
28        int swapCount = n;
29
30        // Find cycles and determine the minimum number of swaps using cycle decomposition
31        for (int i = 0; i < n; i++) {
32            if (!visited[i]) {
33                swapCount--;
34                int j = i;
35                while (!visited[j]) {
36                    visited[j] = true;
37                    j = valueToIndex.get(nums[j]);
38                }
39            }
40        }
41
42        return swapCount;
43    }
44
45    // Helper function: compute the sum of digits of a number
46    private int f(int x) {
47        int sum = 0;
48        while (x != 0) {
49            sum += x % 10;
50            x /= 10;
51        }
52        return sum;
53    }
54}
55

1class Solution {
2public:
3    // Helper function: calculates the sum of digits of x
4    int f(int x) {
5        int sum = 0;
6        while (x) {
7            sum += x % 10;
8            x /= 10;
9        }
10        return sum;
11    }
12
13    // Main function: returns the minimum number of swaps required
14    int minSwaps(vector<int>& nums) {
15        int n = nums.size();
16        // Create an array of pairs: {digit sum, original number}
17        vector<pair<int, int>> arr(n);
18        for (int i = 0; i < n; ++i) {
19            arr[i] = {f(nums[i]), nums[i]};
20        }
21
22        // Sort the array based on the digit sum (stable if tie)
23        sort(arr.begin(), arr.end());
24
25        // Mapping from number to its index in the sorted array
26        unordered_map<int, int> indexInSorted;
27        for (int i = 0; i < n; ++i) {
28            indexInSorted[arr[i].second] = i;
29        }
30
31        // Visited array to keep track of the swaps
32        vector<char> visited(n, 0);
33        int minSwapCount = n;
34
35        // Cycle decomposition: each cycle of k elements needs (k-1) swaps
36        for (int i = 0; i < n; ++i) {
37            if (!visited[i]) {
38                --minSwapCount;  // Each cycle reduces swap count by one
39                int j = i;
40                while (!visited[j]) {
41                    visited[j] = 1;
42                    // Map to next index according to where nums[j] should be in sorted array
43                    j = indexInSorted[nums[j]];
44                }
45            }
46        }
47        return minSwapCount;
48    }
49};
50

1// Calculates the sum of digits of a given number x.
2function f(x: number): number {
3    let sum = 0;
4    while (x !== 0) {
5        sum += x % 10;
6        x = Math.floor(x / 10);
7    }
8    return sum;
9}
10
11// Calculates the minimum number of swaps needed to sort the array
12// such that for each index i, nums[i] is in the position where
13// the sum of its digits (and its value as tiebreaker) matches the sorted order.
14function minSwaps(nums: number[]): number {
15    const n = nums.length;
16
17    // Create an array of tuples: [digit sum, original value]
18    const arr: [number, number][] = new Array(n);
19    for (let i = 0; i < n; i++) {
20        arr[i] = [f(nums[i]), nums[i]];
21    }
22
23    // Sort the array based on digit sum, then by number itself to break ties
24    arr.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
25
26    // Map each value in the sorted array to its index in the sorted array
27    const posInSorted = new Map<number, number>();
28    for (let i = 0; i < n; i++) {
29        posInSorted.set(arr[i][1], i);
30    }
31
32    // Visited array to track elements already placed correctly through cycles
33    const visited: boolean[] = new Array(n).fill(false);
34
35    // The minimum number of swaps is initialized as length of array
36    let swaps = n;
37
38    // Find cycles in the permutation and count swaps needed
39    for (let i = 0; i < n; i++) {
40        if (!visited[i]) {
41            swaps--;
42            let j = i;
43            // Traverse the cycle and mark nodes as visited
44            while (!visited[j]) {
45                visited[j] = true;
46                // The position for nums[j] in the sorted order
47                j = posInSorted.get(nums[j])!;
48            }
49        }
50    }
51    return swaps;
52}
53

Time and Space Complexity

Time Complexity: The code processes n elements where n = len(nums).
1. The helper function f(x) is called once for each element in nums, so O(n * k) where k is the max number of digits in any x.
2. Computing arr = sorted((f(x), x) for x in nums) combines O(n * k) for mapping with O(n log n) for sorting.
3. Building dictionary d is O(n).
4. The final loop detects cycles in a permutation, which in total visits every index once: O(n).
Therefore, the overall time complexity is O(n * k + n log n) where k is the maximum digit count of an element in nums.
Space Complexity:
1. The arr list has size O(n).
2. The dictionary d has size O(n).
3. The boolean list vis has size O(n).
4. No other significant auxiliary data structures.
Thus, the overall space complexity is O(n)

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know