3551. Minimum Swaps to Sort by Digit Sum LeetCode Solution

Last updated: June 5, 2025

In this guide, you will get 3551. Minimum Swaps to Sort by Digit Sum LeetCode Solution with the best time and space complexity. The solution to Minimum Swaps to Sort by Digit Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Swaps to Sort by Digit Sum solution in C++
Minimum Swaps to Sort by Digit Sum solution in Java
Minimum Swaps to Sort by Digit Sum solution in Python
Additional Resources

3551. Minimum Swaps to Sort by Digit Sum LeetCode Solution image

Problem Statement of Minimum Swaps to Sort by Digit Sum

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.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

3551. Minimum Swaps to Sort by Digit Sum LeetCode Solution in C++

class Solution {
 public:
  int minSwaps(vector<int>& nums) {
    int ans = 0;
    unordered_set<int> seen;
    unordered_map<int, int> numToIndex;
    vector<int> sortedNums = nums;

    ranges::sort(sortedNums, ranges::less{}, [this](int num) {
      return pair<int, int>{getDigitSum(num), num};
    });

    for (int i = 0; i < sortedNums.size(); ++i)
      numToIndex[sortedNums[i]] = i;

    for (int i = 0; i < nums.size(); ++i) {
      if (seen.contains(i) || numToIndex[nums[i]] == i)
        continue;
      int cycleSize = 0;
      int j = i;
      while (seen.insert(j).second) {
        j = numToIndex[nums[j]];
        ++cycleSize;
      }
      ans += max(cycleSize - 1, 0);
    }

    return ans;
  }

 private:
  int getDigitSum(int num) {
    int sum = 0;
    while (num > 0) {
      sum += num % 10;
      num /= 10;
    }
    return sum;
  }
};
/* code provided by PROGIEZ */

3551. Minimum Swaps to Sort by Digit Sum LeetCode Solution in Java

class Solution {
  public int minSwaps(int[] nums) {
    int ans = 0;
    Set<Integer> seen = new HashSet<>();
    Map<Integer, Integer> numToIndex = new HashMap<>();
    int[] sortedNums = Arrays.stream(nums)
                           .boxed()
                           .sorted(Comparator.comparingInt((Integer num) -> getDigitSum(num))
                                       .thenComparingInt(num -> num))
                           .mapToInt(Integer::intValue)
                           .toArray();

    for (int i = 0; i < sortedNums.length; ++i)
      numToIndex.put(sortedNums[i], i);

    for (int i = 0; i < nums.length; ++i) {
      if (seen.contains(i) || numToIndex.get(nums[i]) == i)
        continue;
      int cycleSize = 0;
      int j = i;
      while (seen.add(j)) {
        j = numToIndex.get(nums[j]);
        ++cycleSize;
      }
      ans += Math.max(cycleSize - 1, 0);
    }

    return ans;
  }

  private int getDigitSum(int num) {
    int sum = 0;
    while (num > 0) {
      sum += num % 10;
      num /= 10;
    }
    return sum;
  }
}
// code provided by PROGIEZ

3551. Minimum Swaps to Sort by Digit Sum LeetCode Solution in Python

class Solution:
  def minSwaps(self, nums: list[int]) -> int:
    ans = 0
    seen = set()
    sortedNums = sorted(nums, key=lambda x: (self._getDigitSum(x), x))
    numToIndex = {num: i for i, num in enumerate(sortedNums)}

    for i, num in enumerate(nums):
      if i in seen or numToIndex[num] == i:
        continue
      cycleSize = 0
      j = i
      while j not in seen:
        seen.add(j)
        j = numToIndex[nums[j]]
        cycleSize += 1
      ans += max(cycleSize - 1, 0)
    return ans

  def _getDigitSum(self, num: int) -> int:
    return sum(int(digit) for digit in str(num))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents