3551: Minimum Swaps to Sort by Digit Sum

Difficulty: Medium

Topics: Sorting, Cycle Detection, Graph Theory

Companies: Google, Amazon, Goldman Sachs

Problem Statement

Given an array of distinct positive integers, sort them based on digit sums (ascending). For equal sums, maintain original order of smaller numbers. Return minimum swaps needed.

Example 1

Input: [37,100] → Output: 1
Explanation: Swap 37 and 100 after computing sums (10 vs 1)

Example 2

Input: [22,14,33,7] → Output: 0
Explanation: Already in correct order

Problem Link: View on LeetCode ↗

Approach 1: Cycle Detection (Optimal)

Identify cycles in element positions after sorting to calculate minimum swaps.

Algorithm Steps

Create augmented array with original indices
Sort based on digit sum and value
Track visited nodes to detect cycles
Calculate swaps using cycle size formula: (cycle length - 1)

Complexity Analysis

Time Complexity	Space Complexity
O(n log n)	O(n)

Cycle Detection Solution

class Solution {
public:
    int digitSum(int x) {
        int sum = 0;
        while (x) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }

    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> sortedNums;
        
        for (int i = 0; i < n; ++i)
            sortedNums.emplace_back(nums[i], i);
        
        sort(sortedNums.begin(), sortedNums.end(), [&](auto& a, auto& b) {
            int sumA = digitSum(a.first);
            int sumB = digitSum(b.first);
            return sumA != sumB ? sumA < sumB : a.first < b.first;
        });

        vector<bool> visited(n, false);
        int swaps = 0;
        
        for (int i = 0; i < n; ++i) {
            if (visited[i] || sortedNums[i].second == i)
                continue;
            
            int cycleSize = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = sortedNums[j].second;
                cycleSize++;
            }
            swaps += (cycleSize - 1);
        }
        return swaps;
    }
};

class Solution {
    private int digitSum(int x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }

    public int minSwaps(int[] nums) {
        int n = nums.length;
        int[][] sortedNums = new int[n][2];
        
        for (int i = 0; i < n; i++) {
            sortedNums[i][0] = nums[i];
            sortedNums[i][1] = i;
        }
        
        Arrays.sort(sortedNums, (a, b) -> {
            int sumA = digitSum(a[0]);
            int sumB = digitSum(b[0]);
            if (sumA != sumB) return sumA - sumB;
            return a[0] - b[0];
        });

        boolean[] visited = new boolean[n];
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            if (visited[i] || sortedNums[i][1] == i) continue;
            
            int cycleSize = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = sortedNums[j][1];
                cycleSize++;
            }
            swaps += (cycleSize - 1);
        }
        return swaps;
    }
}

class Solution:
    def digit_sum(self, x: int) -> int:
        s = 0
        while x > 0:
            s += x % 10
            x //= 10
        return s

    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        sorted_nums = sorted(
            [(num, i) for i, num in enumerate(nums)],
            key=lambda x: (self.digit_sum(x[0]), x[0])
        )

        visited = [False] * n
        swaps = 0

        for i in range(n):
            if visited[i] or sorted_nums[i][1] == i:
                continue

            cycle_size = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = sorted_nums[j][1]
                cycle_size += 1

            swaps += (cycle_size - 1)

        return swaps

Optimization Insight: Cycle detection reduces the problem to counting permutation cycles, providing O(n) time complexity after sorting.

Approach 2: Position Mapping with Hash Table

Alternative implementation using hash map for position tracking and in-place swaps.

Algorithm Steps

Create a sorted copy with original indices
Build position map from original to sorted indices
Perform swaps until elements reach correct positions
Count swaps during correction process

Complexity Analysis

Time Complexity	Space Complexity
O(n log n)	O(n)

Hash Map Solution

class Solution {
public:
  int minSwaps(vector<int>& nums) {
    vector<pair<int, int>> arr;
    for (int i = 0; i < nums.size(); ++i) {
      int sum = 0, n = nums[i];
      while (n) {
        sum += n % 10;
        n /= 10;
      }
      arr.emplace_back(sum, nums[i]);
    }

    sort(arr.begin(), arr.end(), [](auto& a, auto& b) {
      return a.first == b.first ? a.second < b.second : a.first < b.first;
    });

    unordered_map<int, int> posMap;
    for (int i = 0; i < arr.size(); ++i)
      posMap[arr[i].second] = i;

    int swaps = 0;
    for (int i = 0; i < nums.size(); ++i) {
      while (posMap[nums[i]] != i) {
        swap(nums[i], nums[posMap[nums[i]]]);
        swaps++;
      }
    }
    return swaps;
  }
};

class Solution {
  public int minSwaps(int[] nums) {
    int[][] arr = new int[nums.length][2];
    for (int i = 0; i < nums.length; i++) {
      int sum = 0, n = nums[i];
      while (n > 0) {
        sum += n % 10;
        n /= 10;
      }
      arr[i] = new int[] { sum, nums[i] };
    }

    Arrays.sort(arr, (a, b) -> {
      if (a[0] == b[0])
        return a[1] - b[1];
      return a[0] - b[0];
    });

    Map<Integer, Integer> posMap = new HashMap();
    for (int i = 0; i < arr.length; i++)
      posMap.put(arr[i][1], i);

    int swaps = 0;
    for (int i = 0; i < nums.length; i++) {
      while (posMap.get(nums[i]) != i) {
        int target = posMap.get(nums[i]);
        int temp = nums[i];
        nums[i] = nums[target];
        nums[target] = temp;
        swaps++;
      }
    }
    return swaps;
  }
}

class Solution:
  def minSwaps(self, nums: List[int]) -> int:
    arr = []
    for num in nums:
      s = sum(int(d) for d in str(num))
      arr.append((s, num))

    arr.sort(key=lambda x: (x[0], x[1]))
    pos_map = {num: i for i, (_, num) in enumerate(arr)}

    swaps = 0
    for i in range(len(nums)):
      while pos_map[nums[i]] != i:
        j = pos_map[nums[i]]
        nums[i], nums[j] = nums[j], nums[i]
        swaps += 1
    return swaps

Note: This approach modifies the original array and has higher constant factors due to hash map operations.

Approach Comparison

Approach	Time	Space	Best Case
Cycle Detection	O(n log n)	O(n)	Large n with many cycles
Position Mapping	O(n log n)	O(n)	Small n with few swaps

Important: Both approaches have same asymptotic complexity but cycle detection is generally more efficient for large inputs.

Edge Cases

1. Single Element

Input: [5] → Output: 0

2. All Elements in Reverse Order

Input: [100, 37] → Output: 1

3. Multiple Same Digit Sums

Input: [19, 28, 37] → Output: 0 (sorted by value)

Testing Tip: Always verify cases where multiple elements have identical digit sums but different values.

Frequently Asked Questions

Why does cycle detection work for swaps?

Each cycle of length k requires (k-1) swaps to fix, as elements can be rotated into place.

How to handle numbers with leading zeros?

Problem states nums[i] are positive integers, so leading zeros don't exist in inputs.

Can we optimize digit sum calculation?

Memoization can help if numbers repeat, but problem states distinct numbers.

What if multiple elements have same value?

Constraints specify distinct positive integers, so values are unique.

Why use original index tracking?

To map where each element needs to go in the sorted permutation.

How does the hash map approach differ?

It performs actual swaps but has higher constant factors due to map lookups.

What's the maximum possible swaps?

Worst case is n-1 swaps (single cycle of length n).

Can we use Union-Find for cycle detection?

Possible but unnecessary complexity for this problem.

How to handle very large numbers?

Digit sum calculation remains O(digits) which is manageable for 1e9 (max 10 digits).

Why sort by value for equal sums?

Problem requires smaller numbers to appear first when sums are equal.

Final Analysis: The cycle detection method provides the most efficient and elegant solution, leveraging sorting and graph theory concepts to achieve optimal performance.