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.
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
, wheren
is the array length andnum_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 EvaluatorExample 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 wheren = len(nums)
.- The helper function
f(x)
is called once for each element innums
, so O(n * k) wherek
is the max number of digits in anyx
. - Computing
arr = sorted((f(x), x) for x in nums)
combines O(n * k) for mapping with O(n log n) for sorting. - Building dictionary
d
is O(n). - 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)
wherek
is the maximum digit count of an element innums
. - The helper function
-
Space Complexity:
- The
arr
list has size O(n). - The dictionary
d
has size O(n). - The boolean list
vis
has size O(n). - No other significant auxiliary data structures.
Thus, the overall space complexity is
O(n)
- The
How many times is a tree node visited in a depth first search?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donโt Miss This!