Find minimum swaps to sort array with duplicates

Q: Find minimum swaps to sort array with duplicates

This is a Coding & Algorithms interview question from Akuna Capital for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

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