Minimum Swaps to Sort by Digit Sum
MedPrompt
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.
Example 1:
Input: nums = [37,100]
Output: 1
Explanation:
- Compute the digit sum for each integer:
[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1] - Sort the integers based on digit sum:
[100, 37]. Swap37with100to obtain the sorted order. - Thus, the minimum number of swaps required to rearrange
numsis 1.
Example 2:
Input: nums = [22,14,33,7]
Output: 0
Explanation:
- Compute the digit sum for each integer:
[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7] - Sort the integers based on digit sum:
[22, 14, 33, 7]. The array is already sorted. - Thus, the minimum number of swaps required to rearrange
numsis 0.
Example 3:
Input: nums = [18,43,34,16]
Output: 2
Explanation:
- Compute the digit sum for each integer:
[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7] - Sort the integers based on digit sum:
[16, 34, 43, 18]. Swap18with16, and swap43with34to obtain the sorted order. - Thus, the minimum number of swaps required to rearrange
numsis 2.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109numsconsists of distinct positive integers.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first determines the final sorted state of the array. Then, it iterates through a copy of the original array, and for each position, if the element is incorrect, it finds the correct element and swaps it into place, counting each swap. This is analogous to a Selection Sort.
Algorithm
- Define a helper function
getDigitSum(int n)to calculate the sum of digits. - Create a copy of the input array,
numsCopy. - Create the target sorted array,
sortedNums, by sortingnumsbased on the custom rule (digit sum, then value). - Initialize
swaps = 0. - Iterate through
numsCopyfromi = 0ton-1. - If
numsCopy[i]is not equal tosortedNums[i]:- Increment
swaps. - Linearly search for
sortedNums[i]innumsCopyfrom indexi+1. Let its index bej. - Swap
numsCopy[i]andnumsCopy[j].
- Increment
- Return
swaps.
Walkthrough
The core idea is to simulate the sorting process using the minimum number of swaps possible, which is what Selection Sort does. First, we need to know the target state, so we create a sorted version of the array, sortedNums, according to the specified rules (digit sum, then value).
Then, we take a copy of the original array, numsCopy, and iterate through it. For each index i, we check if the element numsCopy[i] is the one that should be there, i.e., if numsCopy[i] == sortedNums[i]. If it's not, we know a swap is necessary. We find the correct element (sortedNums[i]) somewhere else in the array (at an index j > i) and swap it with the element at i. We increment our swap counter for each such exchange.
The main drawback is the search for the correct element at each step, which requires a linear scan of the rest of the array, leading to an overall quadratic time complexity.
import java.util.Arrays; class Solution { private int getDigitSum(int n) { int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum; } public int minimumSwaps(int[] nums) { int n = nums.length; Integer[] sortedNumsInteger = new Integer[n]; for (int i = 0; i < n; i++) { sortedNumsInteger[i] = nums[i]; } Arrays.sort(sortedNumsInteger, (a, b) -> { int sumA = getDigitSum(a); int sumB = getDigitSum(b); if (sumA != sumB) { return Integer.compare(sumA, sumB); } else { return Integer.compare(a, b); } }); int[] sortedNums = new int[n]; for (int i = 0; i < n; i++) { sortedNums[i] = sortedNumsInteger[i]; } int[] numsCopy = Arrays.copyOf(nums, n); int swaps = 0; for (int i = 0; i < n; i++) { if (numsCopy[i] != sortedNums[i]) { swaps++; for (int j = i + 1; j < n; j++) { if (numsCopy[j] == sortedNums[i]) { int temp = numsCopy[i]; numsCopy[i] = numsCopy[j]; numsCopy[j] = temp; break; } } } } return swaps; }}Complexity
Time
O(N^2) - The dominant operation is the nested loop structure. The outer loop runs N times, and the inner linear search for the correct element can take up to O(N) time in each iteration. The initial sort takes O(N log N), but it's overshadowed by the O(N^2) swapping part.
Space
O(N) - We need to store a copy of the array and the target sorted array.
Trade-offs
Pros
Conceptually simple and easy to implement.
Directly simulates the process of sorting by swapping elements into their final positions.
Cons
Highly inefficient with a quadratic time complexity.
Will result in a 'Time Limit Exceeded' error for the given problem constraints (N up to 10^5).
This problem can be reframed as finding the minimum number of swaps to sort a permutation. The minimum number of swaps is given by the formula N - C, where N is the number of elements and C is the number of disjoint cycles in the permutation. The approach involves determining the permutation that maps each element from its original position to its sorted position and then counting the cycles in this permutation graph.
Algorithm
- Create a list of pairs,
(value, originalIndex), for each element in the input array. - Sort this list based on the custom rule: primarily by the digit sum of the number (ascending), and secondarily by the number itself (ascending).
- The sorted list implicitly defines a permutation. The element at original index
p.originalIndexmoves to the new indexiwherepissortedList.get(i). - To find the minimum swaps, count the number of cycles in this permutation. Initialize a
visitedarray of sizeN. - Iterate from
i = 0ton-1. Ifihas not been visited, start a traversal fromi, following the permutation links and marking nodes as visited, until you return to the start. This completes one cycle. Increment a cycle counter. - The minimum number of swaps is
N - numberOfCycles.
Walkthrough
This optimal approach leverages a classic result from combinatorics. The minimum number of swaps to sort any permutation of N elements is N - C, where C is the number of disjoint cycles in the permutation.
First, we need to figure out where each element is supposed to go. We can do this by creating pairs of (value, originalIndex) and sorting these pairs based on the problem's custom sorting rule. After sorting, if we look at the i-th pair, its value is what should be at index i in the final array, and its originalIndex tells us where this value came from.
This gives us a permutation graph where an edge exists from an element's original position to its final position. We can count the number of disjoint cycles in this graph. A cycle is a path that starts and ends at the same index, e.g., A -> B -> C -> A. The number of swaps needed to fix a cycle of length k is k-1.
We can count cycles by iterating through all indices from 0 to N-1. If we find an index that we haven't visited yet, we've found a new cycle. We then traverse this cycle, marking all its nodes as visited, and increment our cycle counter. The final answer is N - totalCycles.
import java.util.*; class Solution { private int getDigitSum(int n) { int sum = 0; int temp = n; while (temp > 0) { sum += temp % 10; temp /= 10; } return sum; } class Pair { int value; int originalIndex; Pair(int value, int originalIndex) { this.value = value; this.originalIndex = originalIndex; } } public int minimumSwaps(int[] nums) { int n = nums.length; List<Pair> indexedNums = new ArrayList<>(); for (int i = 0; i < n; i++) { indexedNums.add(new Pair(nums[i], i)); } // A cache for digit sums can optimize the sorting comparison, // as getDigitSum might be called multiple times for the same number. Map<Integer, Integer> digitSumCache = new HashMap<>(); Collections.sort(indexedNums, (p1, p2) -> { int sum1 = digitSumCache.computeIfAbsent(p1.value, this::getDigitSum); int sum2 = digitSumCache.computeIfAbsent(p2.value, this::getDigitSum); if (sum1 != sum2) { return Integer.compare(sum1, sum2); } else { return Integer.compare(p1.value, p2.value); } }); boolean[] visited = new boolean[n]; int totalCycles = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { totalCycles++; int j = i; while (!visited[j]) { visited[j] = true; // Follow the cycle: the element that should be at sorted position 'j' // came from original position 'indexedNums.get(j).originalIndex'. j = indexedNums.get(j).originalIndex; } } } return n - totalCycles; }}Complexity
Time
O(N log N) - The main bottleneck is sorting the array of pairs. Calculating digit sums for all elements takes O(N * log K) (where K is the maximum value of a number), and counting cycles takes O(N). Thus, the overall complexity is dominated by the sort.
Space
O(N) - We need space to store the list of pairs, a cache for digit sums, and the `visited` array for cycle counting.
Trade-offs
Pros
Optimal time complexity for this problem.
Guaranteed to find the minimum number of swaps.
Handles large inputs efficiently.
Cons
More complex to conceptualize and implement than the naive approach.
Requires understanding of permutation cycles.
Solutions
Solution
class Solution {public int minSwaps(int[] nums) { int n = nums.length; int[][] arr = new int[n][2]; for (int i = 0; i < n; i++) { arr[i][0] = f(nums[i]); arr[i][1] = nums[i]; } Arrays.sort( arr, (a, b)->{ if (a[0] != b[0]) return Integer.compare(a[0], b[0]); return Integer.compare(a[1], b[1]); }); Map<Integer, Integer> d = new HashMap<>(); for (int i = 0; i < n; i++) { d.put(arr[i][1], i); } boolean[] vis = new boolean[n]; int ans = n; for (int i = 0; i < n; i++) { if (!vis[i]) { ans--; int j = i; while (!vis[j]) { vis[j] = true; j = d.get(nums[j]); } } } return ans; }private int f(int x) { int s = 0; while (x != 0) { s += x % 10; x /= 10; } return s; }}class Solution {public: int f(int x) { int s = 0; while (x) { s += x % 10; x /= 10; } return s; } int minSwaps(vector<int> &nums) { int n = nums.size(); vector<pair<int, int>> arr(n); for (int i = 0; i < n; ++i) arr[i] = {f(nums[i]), nums[i]}; sort(arr.begin(), arr.end()); unordered_map<int, int> d; for (int i = 0; i < n; ++i) d[arr[i].second] = i; vector<char> vis(n, 0); int ans = n; for (int i = 0; i < n; ++i) { if (!vis[i]) { --ans; int j = i; while (!vis[j]) { vis[j] = 1; j = d[nums[j]]; } } } return ans; }};class Solution: def minSwaps(self, nums: List[int]) -> int: def f(x: int) -> int: s = 0 while x: s += x % 10 x //= 10 return s n = len(nums) arr = sorted((f(x), x) for x in nums) d = {a[1]: i for i, a in enumerate(arr)} ans = n vis = [False] * n for i in range(n): if not vis[i]: ans -= 1 j = i while not vis[j]: vis[j] = True j = d[nums[j]] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.