Find minimum swaps to sort array with duplicates

Problem

Given an integer array nums of length n that may contain duplicate values, you may perform swaps where you choose any two indices i and j and swap nums[i] and nums[j].

Return the minimum number of swaps required to reorder nums into non-decreasing order.

Input

• An integer array nums.

Output

• An integer: the minimum number of swaps needed to make nums sorted in non-decreasing order.

Constraints

• 1 <= n <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

Notes

• Because duplicates exist, there can be multiple valid sorted targets; your answer should be the minimum swaps over all valid ways to reach a sorted array.

Examples

1. nums = [2, 1, 2] → sorted form is [1, 2, 2], answer 1 (swap indices 0 and 1).
2. nums = [1, 5, 1, 5] → answer 1 (swap the two middle elements to get [1,1,5,5]).

Find minimum swaps to sort array with duplicates

Hints

1. Sort a copy of nums to get the target. Map this to a permutation problem: minimum swaps to realize a permutation is (#elements that move) - (#cycles).
2. With duplicates you may choose which equal element goes to which equal slot. To minimize swaps you want to MAXIMIZE the number of cycles, so model it on VALUES: add an edge value_here -> value_that_belongs_here for every out-of-place position.
3. Every 2-cycle (a pair of values pointing at each other) is the shortest possible cycle and can always be taken first. After removing all 2-cycles, decompose each remaining component into as many cycles as possible. Beware: greedy shortest-cycle-first is NOT always optimal -- e.g. [2,4,3,6,5,1,3,2,1] needs an exact decomposition (answer 6).