Scale Engineer

Minimum Swaps to Sort by Digit Sum

Med
#3162Time: 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.
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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]. Swap 37 with 100 to obtain the sorted order.
  • Thus, the minimum number of swaps required to rearrange nums is 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 nums is 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]. Swap 18 with 16, and swap 43 with 34 to obtain the sorted order.
  • Thus, the minimum number of swaps required to rearrange nums is 2.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums consists 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 sorting nums based on the custom rule (digit sum, then value).
  • Initialize swaps = 0.
  • Iterate through numsCopy from i = 0 to n-1.
  • If numsCopy[i] is not equal to sortedNums[i]:
    • Increment swaps.
    • Linearly search for sortedNums[i] in numsCopy from index i+1. Let its index be j.
    • Swap numsCopy[i] and numsCopy[j].
  • 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).

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem