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]).